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

Petr Kolman, Jiří Sgall

Předchozí program semináře [Previous program]

15. 5., 22. 5. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Nikhil Bansal and Arindam Khan: Improved Approximation Algorithm for Two-Dimensional Bin Packing. SODA 2014.
(referuje Jan Voborník)

Abstract: We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Pradel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.

24. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Lukasz Jez: Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling
(joint work with Christoph Durr and Oscar C. Vasque)

Abstract: We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the jobs' deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.

10. 4., 17. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh: Faster Parameterized Algorithms using Linear Programming. arXiv:1203.0833
(referuje Martin Koutecký)

Abstract: We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O((2.618)k) algorithm for the problem. Here k is the excess of the vertex cover size over the LP optimum, and we write O(f(k)) for a time complexity of the form O(f(k)nO(1)), where f(k) grows exponentially with k. We proceed to show that a more sophisticated branching algorithm achieves a runtime of O(2.3146k).
Following this, using known and new reductions, we give O(2.3146k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an O(1.5214k) algorithm for Ko\"nig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The most notable improvement is the new bound for Odd Cycle Transversal - this is the first algorithm which beats the dependence on k of the seminal O(3k) algorithm of Reed, Smith and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most 2kclogk vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

27. 3., 3. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Anupam Gupta, Amit Kumar and Clifford Stein: Maintaining Assignments Online: Matching, Scheduling, and Flows. SODA 2014.
(referuje Pavel Veselý)

Abstract: Consider the following edge-orientation problem: edges of a graph appear online one-by-one and they to be directed - given an "orientation". We want to ensure that the indegree of each vertex remains low. (This is a simple case of scheduling unit-sized jobs on machines, where each job can only go on one of two machines.) If the edge-orientations we assign are irrevocable, we su ffer a signi cant loss in quality due to online decision-making (as compared to the offline performance). For instance the best online competitive ratio achievable is Theta(log m) for even this toy problem. But what if the decisions are not irrevocable - what if we allow a limited number of reassignments? Can we do much better? We show that indeed we can. For instance, for edge-orientation, we can achieve a constant-competitive load while doing only a constant number of re-orientations per edge (in an amortized sense). For more substantial problems, our results are as follows:

13. 3., 20. 3. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

René Sitters: Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. SODA 2014.
(referuje Dušan Knop)

Abstract: We give a polynomial time, (1+eps)-approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane, on weighted planar graphs, and on weighted trees. This improves on the known quasi-polynomial time approximation schemes for these problems. The algorithm is based on a simple technique that reduces the TRP to what we call the segmented TSP. Here, we are given numbers l1, …, lK and n1, …, nK and we need to find a path that visits at least nh points within path distance lh from the starting point for all h ∊ {1, …, K}. A solution is α-approximate if at least nh points are visited within distance αlh. It is shown that any algorithm that is alpha-approximate for every constant K in some metric space, gives an alpha(1+eps)-approximation for the TRP in the same metric space. Subsequently, approximation schemes are given for this segmented TSP problem in different metric spaces. The segmented TSP with only one segment (K = 1) is equivalent to the k-TSP for which a (2+eps)-approximation is known for a general metric space. Hence, this approach through the segmented TSP gives new impulse for improving on the 3.59-approximation for TRP in a general metric space. A similar reduction applies to many other minimum latency problems. To illustrate the strength of this approach we apply it to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, 1|precwjCj, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem. Both approximation schemes apply as well if release dates are added to the problem.

27. 2., 6. 3. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Marek Cygan: Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. FOCS 2013. Also arXiv:1304.1424.
(referuje Martin Böhm)

Abstract: One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-Set Packing is the well known 3-Dimensional Matching problem. Both problems belong to the Karp`s list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-Set Packing is (k + eps)/2 and goes back to the work of Hurkens and Schrijver [SIDMA`89], which gives (1.5 + eps)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps.
The main result of the paper is a new approach to local search for k-Set Packing where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c^r poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k + 1 + eps)/3-approximation algorithm, improving the best known approximation ratio for k-Set Packing. In particular we improve the approximation ratio for 3-Dimensional Matching from 3/2 + eps to 4/3 + eps.