KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Mon, 08 Oct 2012 15:25:13 +0200Mon, 08 Oct 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 +0200Online Delay Management
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197
We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of delta. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by delta. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays delta_1 and delta_2, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Delta a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.Sven O. Krumke; Clemens Thielen; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197Thu, 08 Jul 2010 08:52:34 +0200