Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Předchozí program semináře, zimní semestr 2013 [Previous program, Fall 2013]

17. 12. 2013, 7. 1. 2014 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Thomas Rothvoss: A simpler proof for O(congestion + dilation) packet routing. IPCO 2013.
(referuje Pavel Veselý)

Abstract: In the store-and-forward routing problem, packets have to be routed along given paths such that the arrival time of the latest packet is minimized. A groundbreaking result of Leighton, Maggs and Rao says that this can always be done in time O(congestion+dilation), where the congestion is the maximum number of paths using an edge and the dilation is the maximum length of a path. However, the analysis is quite arcane and complicated and works by iteratively improving an infeasible schedule. Here, we provide a more accessible analysis which is based on conditional expectations. Like [LMR94], our easier analysis also guarantees that constant size edge buffers suffice. Moreover, it was an open problem stated e.g. by Wiese [Wie11], whether there is any instance where all schedules need at least (1+eps)(congestion+dilation) steps, for a constant eps>0. We answer this question affirmatively by making use of a probabilistic construction.

10. 12. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Hans Kellerer, Vladimir Kotov: An efficient algorithm for bin stretching. Oper. Res. Lett. 41(4): 343-346 (2013).
(referuje Emese Bittner)

Abstract: A sequence of items that can be packed into mm bins of unit size has to be assigned online to the bins minimizing the stretching factor, i.e., to stretch the bin sizes as little as possible such that the items fit into the bins. We present an elementary algorithm with stretching factor 11/7 improving the best known algorithm by Cheng et al. (2005) [5] with a stretching factor of 1.6. Our algorithm uses simple but efficient techniques of grouping the bins in batches of similar structure.

26. 11., 3. 12. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Jiří Sgall: Optimal analysis of Best Fit bin packing
(joint work with G. Dósa)

Abstract: In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. BestFit algorithm packs each item into the most full bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of BestFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for BestFit bin packing is exactly 1.7, improving the previous bound of 1.75. This means that if the optimum needs OPT bins, BestFit always uses at most \floor(1.7 OPT) bins. Furthermore we show matching lower bounds for all values of OPT, i.e., we give instances on which BestFit uses exactly \floor(1.7 OPT) bins. Thus we completely settle the worst-case complexity of BestFit bin packing after more than 40 years of its study.

19. 11. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Yasmina Seddik: A polynomial time OPT-1 algorithm for a scheduling problem with two delivery dates and cumulative payoffs. MISTA 2013

Abstract: We consider a single machine scheduling problem where jobs have a common stepwise payoff function, and where release dates are considered. This problem is strongly NP-hard. We showed that there exists a polynomial time approximation algorithm with absolute guarantee K(K-1)/2, i.e. OPT<=APPROX+K(K-1)/2 as it is a maximization problem (where K is the number of breakpoints of the common stepwise payoff function). For the sake of clarity, in this talk we will focus on the proof for the case where K=2, which relies on the same principles as the general proof.

5. 11., 12. 11. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Michel X. Goemans and Thomas Rothvoss: Polynomiality for Bin Packing with a Constant Number of Item Types. SODA 2014. Also http://arxiv.org/abs/1307.5108.
(referuje Martin Koutecký)

Abstract: We consider the bin packing problem with d different item sizes s_i and item multiplicities a_i, where all numbers are given in binary encoding. This problem formulation is also known as the 1-dimensional cutting stock problem. In this work, we provide an algorithm which, for constant d, solves bin packing in polynomial time. This was an open problem for all d >= 3. In fact, for constant d our algorithm solves the following problem in polynomial time: given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.

15. 10., 22. 10. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Lukas Polacek and Ola Svensson: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation. ICALP 2012.
(referuje Martin Böhm)

Abstract. The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. proved that a certain configuration LP can be used to estimate the optimal value within a factor ${1}/{(4+\epsilon)}$, for any $\epsilon>0$, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee.
A natural question that arises from their work is if the difference between these guarantees is inherent or because of a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. and provide a novel analysis that lets us significantly improve the bound on its running time: from $2^{O(n)}$ to $n^{O(\log n)}$. Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.

8. 10. 2013 (úterý [Tuesday], 9:00, MFF UK Malá Strana S10)

Pavel Veselý: Competitiveness of Fit Algorithms for Black and White Bin Packing

Abstract. In the Bin Packing problem a sequence of items of size up to one must be packed into the minimum number of unit capacity bins. We focus on a variant of Bin Packing in which the items have two colors, black and white, therefore called Black and White Bin Packing. We study the online setting of the problem and show the 3-competitiveness of fit algorithms which try to put an incoming item into a bin whenever it is possible. Moreover, when the items have size at most 1/d for d>=2 we show that the Worst Fit algorithm is (1+d/(d-1))-competitive.