## 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.

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 |

Date of the Publication (Server): | 2012/10/08 |

Number of page: | 24 |

Faculties / Organisational entities: | 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 |