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 2017 [Previous program, Fall 2017]

5. 1. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Moses Charikar, Konstantin Makarychev, Yury Makarychev: Integrality Gaps for Sherali-Adams Relaxations. STOC 2009.
(presented by Jakub Sosnovec)

Abstract: We prove strong lower bounds on integrality gaps of Sherali-Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive nδ rounds of lift and project. For MAX CUT and Vertex Cover, these show that even nδ rounds of Sherali-Adams do not yield a better than 2-ε approximation. The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. We develop a conceptually simple geometric approach to constructing Sherali-Adams gap examples via constructions of consistent local SDP solutions. This geometric approach is surprisingly versatile. We construct Sherali-Adams gap examples for Unique Games based on our construction for MAX CUT together with a parallel repetition like procedure. This in turn allows us to obtain Sherali-Adams gap examples for any problem that has a Unique Games based hardness result (with some additional conditions on the reduction from Unique Games). Using this, we construct 2-ε gap examples for Maximum Acyclic Subgraph that rules out any family of linear constraints with support at most nδ.

15. 12., 22. 12. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Ola Svensson, Jakub Tarnawski, László A. Végh: A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem. https://arxiv.org/abs/1708.04215.
(presented by Pavel Veselý)

Abstract: We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

8. 12. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Andreas Emil Feldmann: Parameterized approximation algorithms for directed Steiner network problems in bidirected graphs

Abstract: Given an edge-weighted directed graph G=(V,E) and a set of d terminal pairs (s_1,t_1),...,(s_d,t_d), the objective of the Directed Steiner Network (DSN) problem is to compute the cheapest subgraph N of G such that there is an s_i -> t_i path in N for every i. This problem is notoriously hard, even in the realm of parameterized approximation: for the well-studied parameter k=|{s_i,t_i}|, i.e. the number of terminals, it was recently shown by [Dinur & Manurangsi, 2017] that under Gap-ETH no d^{1/4-o(1)}-approximation is possible for DSN in f(k)*poly(n) time, for any function f(k). The main question we explore is: what approximation factors and runtimes are possible for special cases of DSN when parametrizing by the number of terminals k?

For problems related to DSN it has been fruitful before to analyze the structure of the optimum in order to obtain approximation and FPT algorithms. Therefore, we consider the DSN_K problem, where we need to compute the optimum network contained in some class K of graphs. If K for instance is the class of planar graphs, then this generalizes several well-studied special cases, such as DSN on planar input graphs, but also the Directed Steiner Tree problem on general input graphs. Our main result proves that if additionally the input is bidirected, then a parameterized approximation scheme exists if we aim to compute the planar optimum. We also provide several hardness results that show that our obtained runtime is the best possible for this special case, while at the same time no parameterized approximation scheme exists for any generalization of this special case. We also consider the Strongly Connected Steiner Subgraph (SCSS) problem as another special case, which cannot be captured by DSN_K for any non-trivial class K. We prove that a known parameterized 2-approximation is best possible for SCSS, and that on bidirected input graphs the problem is FPT for parameter k.

10. 11., 24. 11. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Ola Svensson: Approximating ATSP by Relaxing Connectivity. FOCS 2015. Also https://arxiv.org/abs/1502.02051.
(presented by Martin Böhm)

Abstract: The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments are constructive and give a constant factor approximation algorithm for these metrics. We remark that the considered case is more general than the directed analog of the special  case of the symmetric traveling salesman problem for which there were recent improvements on Christofides' algorithm.

27. 10., 3. 11. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Syamantak Das and Andreas Wiese: On minimizing the makespan when some jobs cannot be assigned on the same machine. ESA 2017.
(presented by Jan Voborník)

Abstract: We study the classical scheduling problem of assigning jobs to machines in order to minimize the makespan. It is well-studied and admits an EPTAS on identical machines and a (2-1/m)-approximation algorithm on unrelated machines. In this paper we study a variation in which the input jobs are partitioned into bags and no two jobs from the same bag are allowed to be assigned on the same machine. Such a constraint can easily arise, e.g., due to system stability and redundancy considerations. Unfortunately, as we demonstrate in this paper, the techniques of the above results break down in the presence of these additional constraints. Our first result is a PTAS for the case of identical machines. It enhances the methods from the known (E)PTASs by a finer classification of the input jobs and careful argumentations why a good schedule exists after enumerating over the large jobs. For unrelated machines, we prove that there can be no (log n)^{1/4-epsilon}-approximation algorithm for the problem for any epsilon > 0, assuming that NP nsubseteq ZPTIME(2^{(log n)^{O(1)}}). This holds even in the restricted assignment setting. However, we identify a special case of the latter in which we can do better: if the same set of machines we give an 8-approximation algorithm. It is based on rounding the LP-relaxation of the problem in phases and adjusting the residual fractional solution after each phase to order to respect the bag constraints.

13. 10., 20. 10. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Pavel Veselý: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
(joint work with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar)

Abstract: We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This probl em has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX- hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the assumed p arameter.

We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For neither of these an EPTAS is likely to exist for the studied parameter: for Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that computing a constant approximation for this parameter is W[1]- hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.

6. 10., 13. 10. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)

Petr Kolman: The length bounded cut problem

Abstract: Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L$, an $L$-bounded cut is a subset $F$ of edges such that the every path between $s$ and $t$ in $(V,E-F)$ has length at least $L$. The minimum $L$-bounded cut problem is to find an $L$-bounded cut of minimum cardinality; the problem is known also under the name the short paths interdiction problem.

The early research on the problem was motivated by an effort to generalize the Max Flow - Min Cut theorem to flows of bounded lenght (i.e., flows decomposable into paths of bounded length). Another motivation for studying the problem were military applications: the goal was to disrupt the movements of enemy troops and material in a capacitated supply network. Later, the problem was also studied in the context of communication networks where the length of paths is often an issue.

Though the problem is very simple to state and has been studied since the beginning of the 70's, it is not much understood yet. 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 for general graphs has approximation ratio, in terms of $n$, only $\Theta(n^{2/3})$.

We will survey known results about the problem and present several new ones. In particular, we will show that for planar and for bounded genus graphs, the problem is fixed parameter tractable (FPT) with respect to $L$, and for graphs of treewidth bounded by $\tau$, we describe $\tau$-approximation algorithm for a vertex version of the problem. We will also discuss related open problems.