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

Petr Kolman, Jiří Sgall

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

12. 12., 19. 12. 2007 (středa [Wednesday], 15:40, MFF UK Malá Strana)

Jan Vondrák: Submodularity in Combinatorial Optimization. PhD. thesis, 2007.
(referuje Tomáš Ebenlendr)

Abstract: This thesis deals with several problems either explicitly or implictly involving the notion of submodularity. We begin by studying the problem of maximizing a single submodular function without any constraints. We proceed to variants of submodular maximization under various constraints. The most flexible and interesting type of constraint seems to be a matroid constraint. We study the problem of maximizing a submodular function subject to a matroid constraint. This framework captures a number of special cases of interest, whichwe examine in more detail. 

28. 11. 2007 (středa [Wednesday], 15:40, MFF UK Malá Strana)

Christoph Durr, Mathilde Hurand: Finding total unimodularity in optimization problems solved by linear programs.
(referuje Ondřej Zajíček)

Abstract:  A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with same cost from the fractional solution. Examples are two scheduling problems and the single disk prefetching/caching problem. We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.

21. 11. 2007 (středa [Wednesday], 15:40, MFF UK Malá Strana)

Artur Czumaj and Andrzej Lingas: Finding a Heaviest Triangle is not Harder than Matrix Multiplication. SODA 2007.
(referuje Tomáš Vyskočil)

Abstract: We show that for any ǫ > 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ǫ), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous time-bounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximum-weight one) in a graph.

31. 10., 7. 11., 14. 11. 2007 (středa [Wednesday], 15:40, MFF UK Malá Strana)

N. Bansal, M. Sviridenko: The Santa Claus Problem. STOC 2006
(referuje Tomáš Ebenlendr)

Abstract: We consider the Santa Claus problem where there are k kids and n items and kid i has utility p_ij for item j. The overall utility of a kid is the sum of all items assigned to it and the goal is to maximize the minimum utility of all kids. We give an O(log log k/log log log k) approximation for the restricted assignment case, where p_ij \in {p_j,0} (i.e. for each item j, some subset S_j of kids care for it and have value p_j and rest have value 0). The guarantee is based on rounding a certain natural exponential sized configuration LP. We also show an integrality gap of k^{1/2} for the general case.

24. 10. 2007 (středa [Wednesday], 15:40, MFF UK Malá Strana)

Petr Kolman: O tocích po krátkých cestách (Length-Bounded Cuts and Flows)
(joint work with  Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Kohler, Ondrej Pangrac, Heiko Schilling, Martin Skutella)

Abstract: For a given number $L$, an $L$-length-bounded cut in a graph $G$ with source $s$ and sink $t$ is a cut that hits all $s$-$t$-paths of length at most $L$. An $L$-length-bounded flow is a flow that can be decomposed into flow paths of length at most $L$. In contrast to the classical flow theory, we describe instances for which the minimum $L$-bounded edge cut is $\Theta(n^{2/3})$-times larger than the maximum $L$-bounded flow where~$n$ denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is \NP-hard to approximate within a factor of at least $1.1377$ for $L\ge 5$ in the case of node-cuts and for $L\ge 4$ in the case of edge-cuts. We also describe algorithms with approximation ratio $\min\{L,n/L\}\leq\sqrt{n}$ in the node case and $\min\{L,n^2/L^2,\sqrt{m}\}\leq n^{2/3}$ in the edge case, where $m$ denotes the number of edges. We discuss the integrality gaps of the LP relaxations of length-bounded flow and cut problems and present further complexity results and also some open problems.

10. 10., 17. 10. 2007 (středa [Wednesday], 11:00, MFF UK Malá Strana)

Philippe Baptiste and Baruch Schieber:
A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness.
J. of Scheduling 6:395-404, 2003.
(referuje Ondřej Zajíček)

Abstract: We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require 1 or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this tall/small task scheduling problem was unknown before, even for two processors.