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

Petr Kolman, Jiří Sgall

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

21. 12. 2010, 11. 1. 2011 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Jiří Sgall: Bounded space bin packing.
(joint work with Marek Chrobak and Gerhard Woeginger)

Abstract: In bounded space bin packing the algorithm is allowed to have only a constant number of bins open. We present a new proof of a classic result on Best Fit bin packing algorithm, some lower bounds for offline and online algorithms that use only bounded space and an offline 1.5001 approximation algorihtm.

14. 12. 2010, 4. 1. 2011 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Nikhil Bansal and Kirk Pruhs: The Geometry of Scheduling. FOCS 2010.
(referuje Tomáš Ebenlendr)

Abstract: We consider the following general scheduling problem: The input consists of n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow, weighted tardiness, and sum of flow squared. Our main result is a randomized polynomial-time algorithm with an approximation ratio O(log log nP), where P is the maximum job size. We also give an O(1) approximation in the special case when all jobs have identical release times. The main idea is to reduce this scheduling problem to a particular geometric set-cover problem which is then solved using the local ratio technique and Varadarajan's quasi-uniform sampling technique. This general algorithmic approach improves the best known approximation ratios by at least an exponential factor (and much more in some cases) for essentially all of the nontrivial common special cases of this problem. Our geometric interpretation of scheduling may be of independent interest.

30. 11., 7. 12. 2010 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Bjarni Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and Mario Szegedy: Streaming algorithms for independent sets. ICALP 2010.
(referuje Michal Dzetkulič)

Abstract: We find “combinatorially optimal” (guaranteed by the degree-sequence alone) independent sets for graphs and hypergraps in linear space in the semi-streaming model. We also propose a new output-efficient streaming model, that is more restrictive than semi-streaming (n·log^{O(1)} n space) but more flexible than classic streaming (log^{O(1)} n space). The algorithms in this model work in poly-logarithmic space, like in the case of the classical streaming model, but they can access and update the output buffer, treating it as an extra piece of memory. Our results form the first treatment of the classic IS problem in the streaming setting.

16. 11., 23. 11., 30. 11. 2010 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

M. Hajiaghayi, R. Khandekar, G. Kortsarz, and J. Mestre: The checkpoint problem. APPROX 2010.
(referuje Dušan Knop)

Abstract. In this paper we consider the sum checkpoint (SCP) and the maximum checkpoint (MCP) problem. These problem have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O(log n) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O(sqrt(n log n/opt)) for MCP and a hardness of 2 under the assumption P!=NP. The hardness holds for trees, in which case we can obtain an asymptotic approximation factor of 2. Finally we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within c n for some constant c > 0, unless P = NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP-hardness of Gabow (SIAM J. Comp 2007, pages 1648–1671).

9. 11., 16. 11. 2010 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Allan Borodin and Brendan Lucier: On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ICALP 2010.
(referuje Ondřej Zajíček)

Abstract: We study the combinatorial auction (CA) problem, in which m objects are sold to rational agents and the goal is to maximize social welfare. Of particular interest is the special case in which agents are interested in sets of size at most s (s-CAs), where a simple greedy algorithm obtains an s + 1 approximation but no truthful algorithm is known to perform better than O(m/sqrt(log m)). As partial work towards resolving this gap, we ask: what is the power of truthful greedy algorithms for CA problems? The notion of greediness is associated with a broad class of algorithms, known as priority algorithms, which encapsulates many natural auction methods. We show that no truthful greedy priority algorithm can obtain an approximation to the CA problem that is sublinear in m, even for s-CAs with s ≥ 2.

26. 10., 2. 11. 2010 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Klaus Jansen: Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling. STACS 2002.
(referuje Marek Krčál)

Abstract: In this paper we show that approximation algorithms for the weighted independent set and s-dimensional knapsack problem with ratio α can be turned into approximation algorithms with the same ratio for fractional weighted graph coloring and preemptive resource constrained scheduling. In order to obtain these results, we generalize known results by Grötschel, Lovasz and Schrijver on separation, non-emptiness test, optimization and violation in the direction of approximability.

12. 10., 19. 10. 2010 (úterý [Tuesday], 12:20, MFF UK Malá Strana, S7)

Petr Kolman: Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing
(joint work with Christian Scheideler)

Abstract: An elementary $h$-route flow, for an integer $h\geq 1$, is a set of $h$ edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an $h$-route flow is a non-negative linear combination of elementary $h$-route flows. An $h$-route cut is a set of edges whose removal decreases the maximum $h$-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of our contribution is an approximate duality theorem for multicommodity $h$-route cuts and flows, for $h\leq 3$: The size of a minimum $h$-route cut is at least $f/h$ and at most $O(\log^2 k \cdot f)$ where $f$ is the size of the maximum $h$-route flow and $k$ is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum $h$-route cut problem for $h=3$ that has an approximation ratio of $O(\log^2 k)$. Previously, polylogarithmic approximation was known only for $h$-route cuts for $h\le 2$. A key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity flows and cuts. Similar results are shown also for the sparsest multiroute cut problem.