Schedule for: 17w5133 - Approximation Algorithms and the Hardness of Approximation

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In this talk, I will show how any integer linear program (ILP) defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2} can be solved efficiently; even in strongly polynomial time. This is a natural extension of the well-known fact that ILPs with totally unimodular (TU) constraint matrices are polynomial-time solvable, which readily follows by the natural integrality of polytopes defined by a TU constraint matrix and integral right-hand sides. To derive this result we combine several techniques. In particular, the problem is first reduced to a particular parity-constrained ILP over a TU constraint matrix. We then leverage Seymour's decomposition of TU matrices to break this parity-constrained ILP into simpler base problems. Finally, we show how these base problems can be solved efficiently by combinatorial optimization techniques, including parity-constrained submodular minimization, and how to derive an optimal solution to the initial ILP from optimal solutions to base problems. Moreover, I will highlight some of the many open problems in this field and discuss recent results related to possible extensions to larger subdeterminants.

Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MST-interdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of G-R. Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph. This is joint work with Andre Linhares.

An edge-weighted graph G is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in some interesting game theory problems, such as network bargaining games and cooperative matching games, because they characterize instances which admit stable outcomes. Motivated by this, in the last few years many researchers have investigated the algorithmic problem of turning a given graph into a stable one, via edge- and vertex-removal operations. However, all the algorithmic results developed in the literature so far only hold for unweighted instances, i.e., assuming unit weights on the edges of G. We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G yields a stable graph, for any weighted graph G. The algorithm is combinatorial and exploits new structural properties of basic fractional matchings, which may be of independent interest. In contrast, we show that the problem of finding a minimum cardinality subset of edges whose removal from a weighted graph G yields a stable graph, does not admit any constant-factor approximation algorithm, unless P=NP. In this setting, we develop an O(Delta)-approximation algorithm for the problem, where Delta is the maximum degree of a node in G.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. We present improved algorithms for stable instances of various clustering and optimization problems, including k-means, k-median, Max Cut, and Minimum Multiway Cut. We also show several hardness results. The talk is based on joint papers with Haris Angelidakis, Konstantin Makarychev, and Aravindan Vijayaraghavan.

Finding k-clique in a graph can trivially be done in time n^{O(k)}, and this is more or less tight if one assumes the Exponential Time Hypothesis (ETH). Now, given the existence of a clique of much larger size, e.g. exp(exp(exp(k))), can we find a k-clique much faster? Similar questions can be asked for maximum dominating set, maximum induced planar subgraph, and many other problems of this nature. In this work, we show that the answers for these questions are likely to be negative: An n^{o(k)} time algorithm for many of these problems will break the Gap-ETH assumption [Dinur'16, Manurangsi-Raghavendra'16], i.e., it will imply 0.99 approximation for 3SAT that runs in sub-exponential time. Breaking Gap-ETH seems beyond the reach of current algorithmic techniques. [joint work with M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan, to appear in FOCS 2017]

In this talk, we discuss the parameterized complexity of approximating the k-Dominating Set problem, where we are asked to decide whether an input graph G on n vertices has a dominating set of size F(k) * k in time T(k) * poly(n). In particular, we consider the question of whether there is an FPT-approximation algorithm for the k-Dominating Set problem. We show that, unless FPT=W[1], the k-Dominating Set problem admits no such FPT-approximation algorithm, for any non-decreasing functions F and T depending only on k (which can be tower functions). Furthermore, we show that, assuming ETH, the k-Dominating Set problem admits no (log n)^{1/k} approximation algorithm that runs in time n^{o(k)}. Our results are obtained from parameterized PCPs for k-Clique constructed by a simple coding technique. This is a joint work with Pasin Manurangsi (UC Berkeley) and Karthik CS (Weizmann Institute of Science), and it is a continuation of a talk from Parinya, which shows the same result under Gap-ETH.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We show that for any stable matching instance with n men and n women the number of stable matchings is at most C^n for some universal constant C>1. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call mixing. This could be of independent interest in other counting applications. joint work with Anna Karlin and Robbie Weber

I will present a deterministic polynomial time c^n approximation algorithm for the permanent of positive semidefinite matrices where c ~ 4.84. This is through a natural convex programming relaxation and proving a PSD variation of the Van der Waerden's theorem. Joint work with Nima Anari, Shayan Oveis Gharan, and Leonid Gurvitz.

The k-server problem is one of the most well-known and widely studied problems in online algorithms. We present an O(log k)^2-competitive randomized algorithm for the k-server problem on HSTs. A breakthrough of Bansal, Buchbinder, Madry, and Naor gave a poly(log k, log N)-competitive algorithm for HSTs of size N, but no o(k)-competitive algorithm that doesn't depend on N was known. Using this, we obtain a poly(log k, log D)-competitive algorithm for any metric space X, where D is the ratio of the largest to smallest distance in X. Our approach is an instantiation of online mirror descent where the mirror map is a multi-scale entropy. Joint work with Sebastien Bubeck, Michael Cohen, Yin Tat Lee, and Aleksander Madry.

Joint work with Bundit Laekhanukit The high-level goal of survivable network design is to design cheap networks that satisfy giving connectivity requirements even in the preserve of node or edge faults. While many approximation algorithms are known for a variety of such problems in undirected graphs, not much is known for directed ones. In this work we present the first non-trivial approximation algorithm for the 2-edge connectivity generalization of Directed Steiner Tree (DST). Analogously to DST, our approach gives a polylogarithmic approximation in quasi-polynomial time, or an $n^{\epsilon}$ approximation in polynomial time. Our approach is based on a complex LP-rounding algorithm that combines the notion of divergent trees and Zelikosky’s height reduction via a probabilistic mapping.

Approximation algorithms and parameterized algorithms are two well-established ways to deal with NP-hard problems. In the first case, the goal is to compute in polynomial time a solution of cost close to the optimum. In the second case, the goal is to compute an optimal solution in (FPT) time f(k)n^O(1), where k is some parameter of the input. The recent area of parameterized approximation seeks to combine the two approaches by, e.g., aiming for (1+eps)-approximations in f(k,eps)n^g(eps) time. We present such algorithms for three important packing problems: for the Maximum Independent Set of Rectangles problem, for the Unsplittable Flow on a Path problem, and for the Two-Dimensional Knapsack problem with rotations. All three problems are W[1]-hard and hence we do not expect to find an FPT algorithm for them. Also, it seems very difficult to construct a PTAS for them which motivates studying parameterized (1+eps)-approximations for them. joint work with Fabrizio Grandoni and Stefan Kratsch

We consider the line search problem in the base polytope of a submodular function: given a submodular function f and a direction a, the goal is to find the maximum value t such that f - t * a is non-negative. Recently, Gupta et al. [ICPO 2017] showed that the discrete Newton algorithm solves this problem using n^2 submodular function minimizations. In this talk, we present a faster algorithm for the problem. The talk is based on joint work with Huy Nguyen (Northeastern University) and Laszlo Vegh (London School of Economics).

The weighted tree augmentation problem (\WTAP) is a fundamental network design problem. We are given an undirected tree $G = (V,E)$ with $n = |V|$ nodes, an additional set of edges $L$ called \emph{links} and a cost vector $c \in \R^L_{\geq 1}$. The goal is to choose a minimum cost subset $S \subseteq L$ such that $G = (V, E \cup S)$ is $2$-edge-connected. In the unweighted case, that is, when we have $c_\ell = 1$ for all $\ell \in L$, the problem is called the tree augmentation problem (\TAP). Both problems are known to be \APX-hard, and the best known approximation factors are $2$ for \WTAP by (Frederickson and J\'aJ\'a, '81) and $\tfrac{3}{2}$ for \TAP due to (Kortsarz and Nutov, TALG '16). Adjashvili (SODA~'17) recently presented an $\approx 1.96418+\eps$-approximation algorithm for \WTAP\ for the case where all link costs are bounded by a constant. This is the first approximation with a better guarantee than $2$ that does not require restrictions on the structure of the tree or the links. In this paper, we improve Adjiashvili's approximation to a $\tfrac{3}{2}+\eps$-approximation for \WTAP under the bounded cost assumption. We achieve this by introducing a strong \LP that combines \zhcgcuts for the standard \LP for the problem with bundle constraints from Adjiashvili. We show that our \LP can be solved efficiently and that it is exact for some instances that arise at the core of Adjiashvili's approach. This results in the improved performance guarantee of $\tfrac{3}{2}+\eps$, which is asymptotically on par with the result by Kortsarz and Nutov. Our result also is the best-known \LP-relative approximation algorithm for \TAP.

Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. In this talk I will survey some recent results, with a focus on low-stretch spanners (from SODA '16) and on spanners with demands (from SODA '17). But I will mostly describe the gaps and open problems which remain, including open questions on the power of linear and semidefinite relaxations for these kinds of network design problems. I will also discuss some recent results on approximation algorithms for optimizing distance oracles (the natural data-structure version of spanners). I will discuss some preliminary results from ITCS '17, including an O(log n)-approximation for optimizing stretch-3 Thorup-Zwick distance oracles. Again, though, I will mostly focus on the many interesting open problems remaining in approximation algorithms for optimizing data structures. Joint work with Zeyu Zhang, Eden Chlamtac, Guy Kortsarz, and Bundit Laekhanukit.

For every epsilon > 0, we give an efficient algorithm to learn the cluster centers of a mixture of poly(k) standard Gaussians in k dimensions, under the condition that every pair of centers is at least k^epsilon apart in Euclidean distance. The best previously known algorithms for this problem are spectral methods, which break down when epsilon = 1/4; i.e. when the centers are separated by k^(1/4), the distance at which clusters may be separated by computing pairwise distances of all the samples. We use the sum of squares method to show that the means remain efficiently learnable when the separation of each pair of means is much smaller. Our algorithm draws on many ideas from the approximation algorithms literature; in particular it relies on sum-of-squares proofs of Gaussian hypercontractivity inequalities first proved to analyze unique games integrality gaps. Joint work with Jerry Li

I will talk about learning hidden communities in the presence of modeling errors in the Stochastic Block Model. This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige—Kilian or monotone errors, and edge outlier errors. In the talk, I will present a simple SDP-based algorithm for finding planted communities in sparse graphs from the Stochastic Block Model and prove that this algorithm is robust to adversarial errors. The talk is based on a joint work with Yury Makarychev and Aravindan Vijayaraghavan (COLT 2016).

We consider a scheduling problem where jobs drawn from a distribution arrive over time and scheduling decisions must be made in an online fashion. The scheduler's goal is to maximize the total value of scheduled jobs. We focus on designing posted price based algorithms -- at every point of time, the algorithm specifies prices for different starting times and job lengths, and the arriving job chooses where to get placed. This model is related but not identical to prophet inequalities. I will present upper and lower bounds on the competitive ratio of pricing based algorithms. I will also describe an intriguing open question.

Recent developments in local search analysis have yielded the first polynomial-time approximation schemes for the k-Means, k-Median, and Uncapacitated Facility Location problems (among others) in a variety of specific classes of metrics . An important extension of these problems is to the setting with outliers. That is, we we are given an additional parameter Z and may discard up to Z points/clients in the input. This is especially important in the setting of k-Means clustering where even a small fraction of outliers may cause a noticeable deviation in the centroids of near-optimum solutions. I will start with a brief review of our work from last year in local search analysis for k-Means clustering in Euclidean metrics. Then I will present a more recent development: a general framework for adapting local search analysis for clustering problems to get approximations for their variants with outliers. In particular, we obtain the following results for clustering in doubling metrics (including constant-dimensional Euclidean metrics) and shortest path metrics of bounded genus graphs. 1) PTASes for uniform opening cost UFL with outliers and 2) bicriteria PTASes that open (1+eps)*k centres for k-Median and k-Means clustering with outliers. There is no violation on the given bound for outliers in any of these approximations. This is joint work with Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour.

We consider fractional covering problems with Lq-norm objectives, where the covering requirements arrive online. This can be viewed as a convex programming problem, and we provide a log-competitive algorithm based on a primal-dual approach. This result expands the class of convex programs with good online algorithms. As applications, we obtain online algorithms for non-uniform buy-at-bulk network design and throughput maximization under Lq-norm capacities.

In this talk, we analyze a semidefinite programming relaxation of the traveling salesman problem due to de Klerk, Pasechnik, and Sotirov. Our main result is that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with the number of cities on the tour. To obtain this result, we search for feasible solutions within a highly structured class of cost matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, they imply several corollaries that help us better understand the semidefinite program and its relationship to other linear and semidefinite relaxations of the traveling salesman problem. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik for the k-cycle cover problem also has an unbounded integrality gap.

We study the hardness of the Node-Disjoint Paths (NDP) problem. In this problem, we are given a graph and a collection of source-sink pairs of vertices, called demand pairs. The goal is to route as many of the demand pairs as possible, along paths which are disjoint in their vertices. The best current algorithm for NDP achieves a factor O(\sqrt{n})-approximation. In a recent work, we showed a 2^{\Omega(\sqrt{log n})}-hardness of approximation for NDP, improving the best previous hardness bound of roughly \Omega(\sqrt{\log n}) by Andrews et al. This new hardness result holds even for subgraphs of grid graphs, but unfortunately it does not extend to grids themselves. The question of approximability of NDP on grid graphs has remained widely open, with the best current upper bound of O(n^{1/4}), and the best current lower bound of APX-hardness. In this talk I will present a new result that comes close to resolving the approximability of NDP in general, and of NDP grids in particular. We show that NDP is hard to approximate to within near-polynomial factors, even in grid graphs. We also obtain similar hardness of approximation results for the closely related Edge-Disjoint Paths (EDP) problem, even in wall graphs. Joint work with Julia Chuzhoy and David H. K. Kim.

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by \Omega( log n / (log log n)) levels of the of the Sherali-Adams hierarchy on instances of size n. It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.. Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than the basic LP, which can be thought of as the base level of the Sherali-Adams hierarchy. This essentially gives a dichotomy result for approximation of CSPs by polynomial size LP extended formulations. Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which \Omega(log log n) levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to \Omega(log n / (log log n)) levels. Joint work with Mrinalkanti Ghosh.

It is well-known that semidefinite programs (such as the Sum-of-Squares or SoS semidefinite programming relaxation) capture spectral arguments. A recent line of work has shown that the reverse is also true for many average-case problems: spectral algorithms are just as powerful as SoS for planted clique, refuting random CSPs, spiked random tensors, and more. In this talk, I will discuss a recent result which shows the equivalence of SoS and spectral algorithms is not a coincidence, and can be shown in a black-box fashion for a broad class of average-case problems. Based on joint work with Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra and David Steurer.

The Paulsen problem is a basic open problem in operator theory: Given vectors u_1, ..., u_n in R^d that are eps-close to satisfying the Parseval's condition and the equal norm condition, is it close to a set of vectors v_1, ..., v_n in R^d that exactly satisfy the Parseval's condition and the equal norm condition Given u_1, ..., u_n, we consider the squared distance to the set of exact solutions. Previous results show that the squared distance of any eps-close solution is at most O(poly(d,n,eps)) and there are eps-close solutions with squared distance at least Omega(d eps). The fundamental open question is whether the squared distance can be independent of the number of vectors n. We answer this question affirmatively by proving that the squared distance of any eps-close solution is O(d^7 eps). Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any eps-close solution is O(d^2 n eps). Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an eps-close solution is O(d^3 eps) when n is large enough and eps is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyzing the operator scaling algorithm.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.