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

  • Export Bibtex
  • Export RIS
Metadaten
Author:Sven Krumke, Clemens Thielen
URN (permanent link):urn:nbn:de:hbz:386-kluedo-32901
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (145)
Document Type:Article
Language of publication:English
Publication Date:2012/10/08
Year of Publication:2012
Publishing Institute:Technische Universität Kaiserslautern
Number of page:24
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:519 Wahrscheinlichkeiten, angewandte Mathematik
MSC-Classification (mathematics):90C27 Combinatorial optimization

$Rev: 12793 $