We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-k-subgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of size roughly n^d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program.
We consider Multiway Cut, a basic graph partitioning problem in which the goal is to find the minimum weight collection of edges disconnecting a given set of special vertices called terminals. Multiway Cut admits a well-known simplex embedding relaxation, where rounding this embedding is equivalent to partitioning the simplex. Current best known solutions to the problem are comprised of a mix of several different ingredients, resulting in intricate algorithms. Moreover, the best of these algorithms is too complex to fully analyze analytically and its approximation factor was verified using a computer. We propose a new approach to simplex partitioning and the Multiway Cut problem based on general transformations of the simplex that allow dependencies between the different variables. Our approach admits much simpler algorithms, and in addition yields an approximation guarantee for the Multiway Cut problem that (roughly) matches the current best computer verified approximation factor.
We will survey some ways that linear programming relaxations can capture optimal strategies in (discrete) stochastic optimization
problems. These problems are often NP-hard or worse, and we will discuss techniques used to develop approximation algorithms for
them. Examples include stochastic knapsack and some budgeted multi-armed bandit problems.
Combinatorial discrepancy has recently found applications in approximation algorithms, and, in particular, in designing new LP rounding algorithms. It can be seen as a common generalization to randomized and iterated rounding, as well as to total unimodularity. In this talk we will give an introduction to combinatorial discrepancy, focusing on the discrepancy of matrices, and its connections to LP rounding. We will describe several beautiful discrepancy minimization algorithms based on geometric random walks. Finally, we will also touch on approximation algorithms for discrepancy itself.
We show that the problem of approximating the covering radius of a lattice, i.e. approximating the largest distance of any point in space from the lattice, up to a constant factor is in coNP assuming the slicing conjecture for Voronoi cells of so-called stable lattices. This improves on the approximation factor of O(sqrt{log n} x stable voronoi slicing) (or O(log^{3/2} n) unconditionally) achieved by Regev & Stephens-Davidowitz (STOC 17), based on their resolution of the reverse Minkowski conjecture.
Our characterization relies upon the canonical filtration of a lattice, as does that of Regev & Stephens-Davidowitz, i.e. canonical way to decompose a lattice along dense lattice subspaces, combined with a convex relaxation of the covering radius due to Dadush & Regev (FOCS 2016). From the algorithmic perspective, we show how to compute an O(log n) approximate version of the canonical filtration in 2^{n+o(n)} time, using discrete Gaussian sampling and a new form of basis reduction that we call filtration reduction.
As a companion contribution, we show that the slicing constant of any Voronoi cell is bounded by O(log^{3/2} n), which complements the O(log n) achieved by Regev & Stephens-Davidowitz for Voronoi cell of stable lattices.
We show that any integer linear program (ILP) that is bimodular, which includes ILPs 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 strongly polynomial-time solvable.
To derive our result we combine several techniques. In particular, starting from an optimal vertex solution v to the natural linear relaxation, we show how v can be rounded in several steps through combinatorial techniques to an optimal integral solution. More precisely, we first reduce the rounding problem 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, which can be rephrased as combinatorial optimization problems and solved with combinatorial techniques, including parity-constrained submodular minimization. Finally, we show how efficient procedures for the base problems can be propagated up through Seymour's TU decomposition to round v to an optimal integral solution.
Recent years have shown remarkable progress in the design and analysis of approximation algorithms for the graphical metric TSP and the general metric case of the s-t-path TSP. We will survey a number of these results, focusing in particular on the s-t-path TSP, where these results have seen the improvements to Christifides' algorithm yield a performance guarantee essentially matching the integrality gap of the standard LP relaxation.
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.
This is joint work with Ola Svensson and Jakub Tarnawski.
We develop polynomial-size LP-relaxations for orienteering and the regret-bounded vehicle routing problem (RVRP) and devise suitable LP-rounding algorithms that lead to various new insights and approximation results for these problems. In orienteering, the goal is to find a maximum-reward r-rooted path, possibly ending at a specied node, of length at most some given budget B. In RVRP, the goal is to find the minimum number of r-rooted paths of regret at most a given bound R that cover all nodes, where the regret of an r-v path is its length - (distance of v from r).
For orienteering without a specified end-node, we introduce a natural bidirected LP-relaxation and obtain a simple 3-approximation algorithm via LP-rounding. This is the first LP-based guarantee for this problem. We also show that point-to-point orienteering (where the end-node is also specified) can be reduced to a regret-version of rooted orienteering at the expense of a factor-2 loss in approximation. For RVRP, we propose two compact LPs that lead to signicant improvements, in both approximation ratio and running time, over the previous O(1)-factor approximation algorithm. One of these LPs is a rather unconventional formulation that leverages various structural properties of an RVRP-solution.
This is joint work with Zachary Friggstad.
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.
Joint Work with Bundit Laekhanukit
In this talk, I will cover some recent progresses on approximating non-preemptive scheduling problems with the total weighted completion time objective, under different machine settings. For many such problems, we give approximation algorithms improving upon the previous state-of-art results that stood for 15 to 20 years. Surprisingly, the improvements are achieved via some natural time-indexed linear programming relaxations, that were not explicitly studied in the literature.
The poise of a spanning tree in an undirected graph is the sum of its diameter and its maximum degree. Finding Steiner trees of minimum poise have applications for the design of fast multicast schemes among the terminals. We present an O(log k) approximation algorithm for minimum poise Steiner tree on k terminals with respect to its natural LP relaxation. This in turn finds use in the first poly-logarithmic approximation algorithms for multicommodity multicast problems in planar graphs. (Details in https://arxiv.org/abs/1612.01492)
Joint work with Jennifer Iglesias (Carnegie Mellon University), Rajmohan Rajaraman (Northeastern) and Ravi Sundaram (Northeastern)
The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Submodular functions are commonly used as utility functions in economics and algorithmic game theory, and they play a major role in combinatorial optimization.
In this talk, I will survey several approaches for maximizing submodular functions. In particular, I will show several recent results that are based on solving multilinear relaxations. These relaxations play the role of linear programming relaxations in linear optimization problems.
We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function.
Our main result is an O(k log n)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(log n), we obtain an O(log^2 n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem and it matches the best approximation known for UFP on trees with a linear objective function.
Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of [Bonsma et al., FOCS 2011; Anagnostopoulos et al., SODA 2014] for UFP on paths with a linear objective. Our relaxation is very structured and we can combine it with the contention resolution framework of [Chekuri et al., STOC 2011]. Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem.
Joint work with Parinya Chalermsook, Alina Ene, and Andreas Wiese.
We consider the problem of maximizing a monotone submodular function subject to a single knapsack constraint. We describe an algorithm that achieves a nearly-optimal 1 - 1/e - eps approximation using (1/eps)^O(1/eps^4) n log^2 n queries to the evaluation oracle for the function. Our algorithm solves the multilinear relaxation for the problem but it avoids a quadratic dependency on the number of value queries by ensuring that the solution has only O(1/eps^4) entries that are strictly fractional (not equal to 0 or 1).
This is joint work with Huy Nguyen (Northeastern University).
In Online Optimization, the data in an optimization problem is revealed over time, and at each step a decision variable needs to be set without knowing the future data. We consider an online optimization setup that includes problems such as online resource allocation with a fixed inventory and the `Adwords' problem popular in online advertising. We consider two broad primal-dual algorithms, with a focus on the competitive ratio, i.e., the ratio of the objective achieved by the algorithm to that of the optimal offline sequence of decisions. We give a bound on this ratio and show how certain smoothing of the objective function can improve the bound; and for separable functions, how to seek the optimal smoothing by solving a convex design problem. This allows us to design effective smoothing customized for a given cost function and problem structure.
Given a finite metric space, the usual k-center problem asks where to place the centers of k unit radius "inflatable" balls such that they cover all the points of the space with as small dilation as possible. This problem has been well understood for more than 3 decades. In this talk we will look at the same question when the balls have different radii. I will try to convince you that this is a natural generalization to study; in particular it generalizes the problem with outliers. Technically, one interesting aspect will be connections to the so-called "firefighter" problem.
Joint work with Prachi Goyal and Ravishankar Krishnaswamy
A classical problem in scheduling is to optimize load balancing objectives in an online assignment of jobs to machines. If the machines have non-uniform speed, then the problem is called scheduling on related machines. In this talk, I will describe a new algorithm for this problem that achieves a constant-competitive assignment for any l-p norm objective. Previous to this work, a constant competitive ratio was known only for the makespan objective (l-infinity norm), via the well-known "slowest-fit" algorithm. Our new algorithm uses gradient descent to solve a convex relaxation of the problem, followed by a rounding technique based on a new framework called machine smoothing. In contrast, most previous relax-and-round algorithms for online problems have employed multiplicative weights to solve the convex relaxation, which incurs a super-constant loss in the competitive ratio. Our techniques also give new results for more general vector scheduling problems. This is joint work with Sungjin Im, Nat Kell, and Maryam Shadloo.
For a given NP-hard combinatorial optimization problem, one may identify interesting subclasses of instances with approximation ratios that are better than those that are known for worst case instances. Such a study can serve two purposes. One is to circumvent hardness of approximation results (in cases where they exist). The other is to guide us towards better worst case approximation algorithms (in cases where hardness of approximation results do not exist). The talk will present examples for these two themes.
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, Yury Makarychev, and Aravindan Vijayaraghavan.
This talk consists of two different but related results. First, we show how to approximate unique games in minor-closed graph families using linear programming and standard low diameter graph decomposition. We will illustrate the proof through the min-uncut problem. Motivated by this result, we consider graph decompositions using effective resistance as the distance measure, and show that every graph (not just minor-free graphs) has a low effective-resistance diameter graph decomposition.
In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is NP-hard for m=3.
We prove that for any fixed epsilon > 0 and m, an LP-hierarchy lift of the time-index LP with a slightly super poly-logarithmic number of rounds provides a (1 + epsilon)-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a (1+epsilon)-approximation in almost quasi-polynomial time. The previously best approximation algorithms guarantee only a 2-approximation for large m.
This is joint work with Elaine Levey.
We present LP relaxations for uniform and non-uniform reordering buffer management, and their application to the design and analysis of competitive online algorithms and polynomial time approximation algorithms for these problems. The talk is based on several joint papers with Noa Avigdor-Elgrabli, Sungjin Im, and Benjamin Moseley.
Given a graph and a set of paths we want to cut (usually implicitly defined), cut problems ask to find the smallest number of edges of vertices that intersect all given paths. We survey recent developments on approximation algorithms and hardness of approximation (assuming the Unique Games Conjecture) for various cut problems, including Directed Multicut, Length-Bounded Cut, and their non-fixed terminal counterparts. We will highlight the efforts to find the optimal LP relaxation for each problem, and introduce a framework that converts their integrality gaps to hardness results.
Based on joint work with Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Chao Xu, and Vivek Madan.
Dependent rounding, originating from the "pipage rounding" work of Ageev and Sviridenko, is now a fundamental algorithmic approach in combinatorial optimization. We survey this area, with an emphasis on the types of correlation inequalities that are achievable/desirable, and applications thereof. Topics covered include connections with matroids, matroid intersection, and scheduling, as well as how to handle situations where some amount of positive correlation is inevitable: the last part is recent joint work with David Harris, Thomas Pensyl, and Khoa Trinh, and arises in facility-location problems.
This talk will be a remote presentation.
The problem of subdeterminant maximization subject to combinatorial constraints arises in various algorithmic and machine learning settings and, recently, convex-programming based estimation algorithms for it have been proposed. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms -- that also output a set -- remained open.
We present novel nonconvex formulations for the constrained subdeterminant maximization problem and prove a new anti-concentration inequality for dependent random variables that together allow us to obtain approximation algorithms for this problem in a variety of settings.
Based on a joint work with Javad Ebrahimi and Damian Straszak available https://arxiv.org/abs/1707.02757
Despite superficial similarities with the determinant, the permanent is #P-hard to compute, even for {0,1}-matrices. A long line of work has focused on designing approximation algorithms for the permanent of matrices with nonnegative entries, culminating with an FPRAS due to Jerrum, Sinclair, and Vigoda.
The permanent has been known to also be nonnegative for another class of matrices, namely positive semidefinite (PSD) matrices. In this talk I will show how to get a c^n approximation algorithm for the permanent of PSD matrices, where c is a universal constant.
Our algorithm is based on a semidefinite program with a convex nonlinear objective. We show that the input matrix can be sandwiched between a diagonal matrix and a rank-1 matrix whose permanents differ by at most a factor of c^n. To obtain the lower bound matrix we use a randomized rounding technique based on projections onto complex gaussian vectors.
If time permits, I will talk about the implications of our result for the recently refuted permanent-on-top conjecture as well as some open problems.
Joint work with Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi.
Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min s − t Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled + or − and the goal is to produce a clustering that agrees with the labels as much as possible: + edges within clusters and − edges across clusters. The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a global objective. We depart from this and study local objectives: minimizing the maximum number of disagreements for edges incident on a single node, and the analogous max min agreements objective. This naturally gives rise to a family of basic min-max graph cut problems. A prototypical representative is Min Max s − t Cut: find an s − t cut minimizing the largest number of cut edges incident on any node. We present the following results:
(1) an O(sqrt{n})-approximation for the problem of minimizing the maximum total weight of disagreement edges incident on any node (thus providing the first known approximation for the above family of min-max graph cut problems),
(2) a remarkably simple 7-approximation for minimizing local disagreements in complete graphs (improving upon the previous best known approximation of 48), and
(3) a 1/(2+ε)-approximation for maximizing the minimum total weight of agreement edges incident on any node, hence improving upon the 1/(4+ε)-approximation that follows from the study of approximate pure Nash equilibria in cut and party affiliation games.
