The Generalized Assignment Problem with Minimum Quantities

  • We consider a variant of the generalized assignment problem (GAP) where 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). We provide several complexity results for different versions of the problem and give polynomial time exact algorithms and approximation algorithms for restricted cases. For the most general version of the problem, we show that it does not admit a polynomial time approximation algorithm (unless P=NP), even for the case of a single bin. This motivates to study dual approximation algorithms that compute solutions violating the bin capacities and minimum quantities by a constant factor. When the number of bins is fixed and the minimum quantity of each bin is at least a factor \(\delta>1\) larger than the largest size of an item in the bin, we show how to obtain a polynomial time dual approximation algorithm that computes a solution violating the minimum quantities and bin capacities by at most a factor \(1-\frac{1}{\delta}\) and \(1+\frac{1}{\delta}\), respectively, and whose profit is at least as large as the profit of the best solution that satisfies the minimum quantities and bin capacities strictly. In particular, for \(\delta=2\), we obtain a polynomial time (1,2)-approximation algorithm.

Download full text files

Export metadata

Metadaten
Author:Sven Krumke, Clemens Thielen
URN:urn:nbn:de:hbz:386-kluedo-32901
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (145)
Document Type:Article
Language of publication:English
Date of Publication (online):2012/10/08
Year of first Publication:2012
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2012/10/08
Page Number:24
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012