The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
• search hit 59 of 246
Back to Result List

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.

• bins.pdf Author: Sven Krumke, Clemens Thielen urn:nbn:de:hbz:386-kluedo-32901 Report in Wirtschaftsmathematik (WIMA Report) (145) Article English 2012/10/08 2012 Technische Universität Kaiserslautern 2012/10/08 24 Fachbereich Mathematik 5 Naturwissenschaften und Mathematik / 510 Mathematik 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization Standard gemäß KLUEDO-Leitlinien vom 10.09.2012