Matching with sizes (or scheduling with processing set restrictions)

Biró, Péter and McDermid, E. (2014) Matching with sizes (or scheduling with processing set restrictions). DISCRETE APPLIED MATHEMATICS, 164 (PART 1). pp. 61-67. ISSN 0166-218X

Preview	Text BiroM10tr.pdf - Draft Version Download (173kB) | Preview
	Text 1-s2.0-S0166218X11004215-main.pdf - Published Version Restricted to Repository staff only Download (246kB) | Request a copy

Abstract

Matching problems on bipartite graphs where the entities on one side may have different sizes are intimately related to scheduling problems with processing set restrictions. We survey the close relationship between these two problems, and give new approximation algorithms for the (NP-hard) variations of the problems in which the sizes of the jobs are restricted. Specifically, we give an approximation algorithm with an additive error of one when the sizes of the jobs are either 1 or 2, and generalise this to an approximation algorithm with an additive error of 2k-1 for the case where each job has a size taken from the set {1,2,4,⋯,2k} (for any constant integer k). We show that the above two problems become polynomial-time solvable if the processing sets are nested. © 2011 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item