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

Petr Kolman, Jiří Sgall

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

5. 1. 2015 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Martin Koutecký: Extended Formulation for Binary CSP that is Compact for Instances of Bounded Treewidth

Abstract: An instance of a binary CSP problem consists of a set of variables, its domains, and a set of constraints, which are binary relations on variables. A graph of an instance is a graph whose vertices are the variables and where two vertices share an edge if the instance contains a constraint over correspoding variables. A binary CSP instance has bounded treewidth if its graph has bounded treewidth. We present an LP formulation of the polytope of all assignemets of a binary CSP instance with bounded treewidth of size |D|^tw (where D is the union of all domains and tw is the treewidth of the instance). This allows one to optimize over (for example) the number of violated constraints. The Binary CSP problem generalizes several important combinatorial optimization problems, for most of which a compact extended formulation was not previously known.

15. 12. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica 36(3): 209-224 (2003)
(referuje Lukáš Folwarczný)

Abstract: We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. In this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski rental-like problems.

1. 12., 8. 12. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Reuven Bar-Yehuda, Dror Rawitz: On the Equivalence Between the Primal-Dual Schema and the Local Ratio Technique. SIAM J. Discrete Math., 19(3), 762–797.
(referuje Pavel Veselý)

Abstract: We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the 2-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent.

24. 11. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Dor Arad, Yael Mordechai, Hadas Shachnai: Tighter Bounds for Makespan Minimization on Unrelated Machines. http://arxiv.org/abs/1405.2530.
(referuje Martin Böhm)

Abstract: We consider the problem of scheduling n jobs to minimize the makespan on m unrelated machines, where job j requires time p_ij  if processed on machine i. A classic algorithm of Lenstra et al. yields the best known approximation ratio of 2 for the problem. Improving this bound has been a prominent open problem for over two decades. In this paper we obtain a tighter bound for a wide subclass of instances which can be identified efficiently. Specifically, we define the feasibility factor of a given instance as the minimum fraction of machines on which each job can be processed. We show that there is a polynomial-time algorithm that, given values L and T, and an instance having a sufficiently large feasibility factor h\in(0,1], either proves that no schedule of mean machine completion time L and makespan T exists, or else finds a schedule of makespan at most T+L/h<2T. For the restricted version of the problem, where for each job j and machine i, p_ij\in{p_j,\infty}, we show that a simpler algorithm yields a better bound, thus improving for highly feasible instances the best known ratio of 33/17+eps, for any fixed eps>0, due to Svensson.

10. 11. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Martin Skutella: A note on the ring loading problem. SODA 2015. Also http://arxiv.org/abs/1405.0789.
(referuje Karel Král)

Abstract: The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than +(19/14)D, where D is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of +(3/2)D. We also present an improved lower bound of +1.1 D (previously +1.01 D) on the best possible bound and disprove a famous long-standing conjecture of Schrijver et al. in this context.

3. 11. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theoretical Computer Science 234, 203–218 (2000)(referuje Lukáš Folwarczný)

Abstract: In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We provide a new, H_k-competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k^2 log k) memory and O(k^2) time per request.

20. 10. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Dušan Knop: Parameterized hardness for length-bounded cuts.

Abstract: I would like to present a parametrized result about length bounded cuts, namely that finding an optimal length bounded cut is W[1]-hard when parameterized by path-width only. I will aslo talk a little bit about some lower bound consequences (assuming ETH). I may also sketch some of our algorithmic results. For example an O(n^k) time algorithm where k is the tree-width and O(f(k) n) time algorithm where k is the size of vertex-cover of the input graph.

13. 10. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Martin Koutecký:  The length bounded cut polytope for series-parallel graphs.
(joint work with Petr Kolman)

Abstract: Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L$, an {\em $L$-bounded cut} is a subset $F$ of edges such that the every path between $s$ and $t$ in $(V,E\set minus F)$ has length at least $L$. The minimum $L$-bounded cut problem is to find an $L$-bounded cut of minimum cardinality.
The problem was first studied around 1970 but still, the problem is not much understood. It is known that the problem is NP-hard and that even finding a 1.1377 approximation is NP-hard. On the other hand, the best known approximation algorithm has approximation ratio, in terms of $n$, only $\Theta(n^{2/3})$. For series-parallel graphs the problem is solvable in polynomial time but the only linear programming relaxation that we are aware of has integrality gap $\Theta(\sqrt{n})$.
We propose and examine a new LP-relaxation (of polynomial size) of the $L$-bounded cut problem and show that all vertices of the associated polytope are integral if the input graph is a series-parallel graph.

6. 10. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Jiří Sgall: Online Competitive Algorithms for Multi-Level Aggregation with Deadlines.
(joint work with Marek Chrobak, Lukáš Folwarczny, and Pavel Veselý)

Abstract: In the Multi-Level Aggregation Problem (MLAPD), requests arrive at the leaves of a weighted tree T each with its own deadline. A service is defined as an arbitrary subtree X of T. This subtree X services all requests that are pending in the nodes of X at the cost equal to the total weight of X. The objective is to minimize the cost of all service sub-trees while keeping all the deadlines. We study online algorithms for MLAPD. For trees of height H we give an online algorithm with competitive ratio 2^O(H).