KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Fri, 10 Aug 2012 15:25:13 +0200Fri, 10 Aug 2012 15:25:13 +0200The Generalized Assignment Problem with Minimum Quantities
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3290
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.Sven Krumke; Clemens Thielenarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3290Mon, 08 Oct 2012 15:25:13 +0200Complexity and Approximability of the Maximum Flow Problem with Minimum Quantities
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3181
We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where
the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which
may depend on the arc. This problem has recently been shown to be weakly NP-complete even on series-parallel graphs.
In this paper, we provide further complexity and approximability results for MFPMQ and several special cases.
We first show that it is strongly NP-hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor.
On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem.
We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still
weakly NP-complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs.
On general graphs, we present a \((2 - 1/\lambda) \)-approximation algorithm for this case, where \(\lambda\) denotes the common minimum quantity of all arcs.Clemens Thielen; Stephan Westphalarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3181Fri, 06 Jul 2012 10:39:47 +0200