TY - GEN
T1 - A constant factor approximation for the generalized assignment problem with minimum quantities and unit size items
AU - Bender, Marco
AU - Thielen, Clemens
AU - Westphal, Stephan
PY - 2013
Y1 - 2013
N2 - We consider a variant of the generalized assignment problem (GAP) where the items have unit size and the amount of space used in each bin is restricted to be either zero (if the bin is not opened) or above a given lower bound (a minimum quantity). This problem is known to be strongly NP-complete and does not admit a polynomial time approximation scheme (PTAS). By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing the first nontrivial approximation result for this problem.
AB - We consider a variant of the generalized assignment problem (GAP) where the items have unit size and the amount of space used in each bin is restricted to be either zero (if the bin is not opened) or above a given lower bound (a minimum quantity). This problem is known to be strongly NP-complete and does not admit a polynomial time approximation scheme (PTAS). By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing the first nontrivial approximation result for this problem.
KW - approximation algorithms
KW - combinatorial optimization
KW - generalized assignment problem
KW - randomized rounding
UR - http://www.scopus.com/inward/record.url?scp=84885227974&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40313-2_14
DO - 10.1007/978-3-642-40313-2_14
M3 - Conference contribution
AN - SCOPUS:84885227974
SN - 9783642403125
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 135
EP - 145
BT - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
T2 - 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
Y2 - 26 August 2013 through 30 August 2013
ER -