Seminář z aproximačních a online algoritmů
Seminar on Approximation and Online Algorithms

Petr Kolman, Jiří Sgall

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

13. 12. 2016, 3. 1. 2017 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi: Make-to-order integrated scheduling and distribution. SODA 2016. Also
(referuje Martin Böhm)

Abstract: Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

29. 11., 6. 12. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also
(referuje Štěpán Šimsa)

Abstract: We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ϵ4+eps. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee.
In this paper we significantly narrow this gap by giving a 1313-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [Hax95] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [AFS12]. For our local search procedure to terminate in polynomial time, we introduce several new ideas such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis. 

22. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Yossi Azar, Ilan Reuven Cohen, Alan Roytman: Online Lower Bounds via Duality,  SODA 2017. Also
(referuje Pavel Veselý)

Abstract: In this paper, we exploit linear programming duality in the online setting (i.e., where input arrives on the fly) from the unique perspective of designing lower bounds on the competitive ratio. In particular, we provide a general technique for obtaining online deterministic and randomized lower bounds (i.e., hardness results) on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight lower bounds for three diverse online problems. The three problems we show tight lower bounds for are the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds.
Our techniques are in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal-dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a primal linear program based on a collection of input sequences, where the objective function corresponds to optimizing the competitive ratio. We then obtain the corresponding dual linear program and provide a feasible solution, where the objective function yields a lower bound on the competitive ratio. Online lower bounds are often achieved by adapting the input sequence according to an online algorithm's behavior and doing an appropriate ad hoc case analysis. Using our unifying techniques, we simultaneously combine these cases into one linear program and achieve online lower bounds via a more robust analysis. We are confident that our framework can be successfully applied to produce many more lower bounds for a wide array of online problems.

15. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski: On routing disjoint paths in bounded treewidth graphs, SWAT 2016. Also
(referuje Filip Šedivý)

Abstract: We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M={(s_1,t_1),...(s_k,t_k)}. The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i,t_i) in M', there is a path in P connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP.
In this paper we obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r3^r) approximation for MaxEDP.

25. 10., 1. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Nikhil Bansal, Daniel Dadush, Shashwat Garg: An Algorithm for Komlós Conjecture Matching Banaszczyk's bound.
FOCS 2016, also
(referuje Martin Böhm)

Abstract: We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)^{1/2}), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t^{1/2} log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log^{1/2} n) bound.

Notes: The presented algorithm is similar to the other cube-walk algorithms for discrepancy of recent years (Bansal's or Lovett and Meka's) but adds some ingenious "energy" constraints that improve the behaviour of the SDP. We will assume basic knowledge of semidefinite programming and its duality (see Gärtner, Bernd, Matoušek, Jiří: Approximation Algorithms and Semidefinite Programming, Springer, 2012.) - but mostly just the fact that (some) semidefinite programs can be closely approximated in polynomial time and that each semidefinite program has a dual which plays a similar role to the linear programming dual (under some conditions).

18. 10. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Jon Lee, Viswanath Nagarajan, and Xiangkun Shen: Max-Cut under Graph Constraints

Abstract: An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G and (ii) edge-weights on a complete undirected graph on the same vertex set. The objective is to find a subset of vertices satisfying some graph-based constraint in G that maximizes the total weight of edges in the cut. The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a 0.5-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali-Adams hierarchy. It can handle any graph constraint for which there is a (certain type of) dynamic program that exactly optimizes linear objectives. Using known decomposition results, these imply essentially the same approximation ratio for GCMC under constraints such as independent set, dominating set and connectivity on a planar graph G (more generally for bounded-genus or excluded-minor graphs).

11. 10. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Pavel Vesely:  Online Chromatic Number is PSPACE-Complete
(joint work with Martin Böhm)
IWOCA 2016 Best Student Paper Award

Abstract: In the online graph coloring problem, vertices from a graph G, known in advance, arrive in an online fashion and an algorithm must immediately assign a color to each incoming vertex v so that the revealed graph is properly colored. The exact location of v in the graph G is not known to the algorithm, since it sees only previously colored neighbors of v. The online chromatic number of G is the smallest number of colors such that some online algorithm is able to properly color G for any incoming order. We prove that computing the online chromatic number of a graph is PSPACE-complete.