12 kwietnia 2022 10:15
[Seminarium ZOK] Kamyar Khodamoradi: "Approximation Algorithms for Demand Strip Packing"
Streszczenie:
In the Demand Strip Packing problem (DSP) we are given a time interval
and a collection of tasks, each one characterized by a processing time
and a demand for a given resource (such as electricity, computational
power etc.). A feasible solution consists of a schedule of the tasks
within the mentioned time interval. Our goal is to minimize the peak
resource consumption, i.e. the maximum total demand of tasks executed
at any point of time. It is known that DSP is NP-hard to approximate
below a factor 3/2, and standard techniques for related problems imply
a (polynomial-time) 2-approximation. Our main result is a 5/3 + ε
approximation for any constant ε > 0. We also achieve best-possible
approximation factors for some relevant special cases.
Appeared in APPROX 2021.
ArXiv link: https://arxiv.org/abs/2105.08577