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