TechTalks from event: IEEE FOCS 2010

51st Annual IEEE Symposium on Foundations of Computer Science

  • Subexponential Algorithms for Unique Games and Related problems Authors: Sanjeev Arora and Boaz Barak and David Steurer
    We give subexponential time approximation algorithms for the unique games and the small set expansion problems. Specifically, for some absolute constant c, we give:

    1 An exp(kn^epsilon)-time algorithm that, given as input a k-alphabet unique game on n variables that has an assignment satisfying 1-epsilon^c fraction of its constraints, outputs an assignment satisfying 1-epsilon fraction of the constraints.

    2. An exp(n^epsilon/delta)-time algorithm that, given as input an n-vertex regular graph that has a set S of delta n vertices with edge expansion at most epsilon^c outputs a set S' of at most delta n vertices with edge expansion at most epsilon.

    We also obtain a subexponential algorithm with improved approximation for the Multi-Cut problem, as well as subexponential algorithms with improved approximations to Max-Cut, Sparsest-Cut and Vertex-Cover on some interesting subclasses of instances.

    Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for unique games. While our results stop short of refusing the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as 3SAT, 3LIN, Label Cover and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio.

    The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every delta>0 and a regular n-vertex graph G, by changing at most delta fraction of G's edges, one can break G into disjoint parts so that the induced graph on each part has at most n^epsilon eigenvalues larger than 1-eta (where epsilon,eta depend polynomially on delta). Our results are based on combining this decomposition with previous algorithms for unique games on graphs with few large eigenvalues (Kolla and Tulsiani 2007, Kolla 2010).

  • Nevanlinna Prize Talk. Laplacian Gems Authors: Dan Spielman
    I will explain some of the most interesting applications of solving linear equations in Laplacian matrices as well as some of the most interesting ideas that have been used in algorithms that solve these equations. The main applications will come from machine learning and optimization. The algorithmic ideas I discuss will include local clustering, sparsification, low-stretch spanning trees, and an under-appreciated technique of Lovasz and Simonovits for bounding the convergence rate of Markov chains.
  • Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures Authors: Chandra Chekuri and Jan Vondrak and Rico Zenklusen
    We consider the problem of randomly rounding a fractional solution $x$ in a polytope $P subset RR^n$ to a vertex $X$ of $P$, so that $E[X] = x$. Our goal is to achieve {em concentration properties} for linear and submodular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two polytopes: the assignment polytope (that is, bipartite matchings and $b$-matchings) cite{S01,GKPS06,KMPS09}, and more recently for the spanning tree polytope cite{AGMGS10}. These schemes have led to a number of new algorithmic results.

    In this paper we describe a new {em swap rounding} technique which can be applied in a variety of settings including {em matroids}, {em matroid intersection} and {em non-bipartite graph $b$-matchings}, while providing Chernoff-type concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use martingale methods to obtain an exponential tail estimate for monotone submodular functions, and also for linear functions in settings where negative correlation does not hold. The rounding scheme explicitly exploits {em exchange properties} of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds.

    The framework of matroids and matroid intersection provides a unifying scheme for several known applications cite{GKPS06,KMPS09,CCPV09,KST09,AGMGS10} as well as new ones, and its flexibility allows a richer set of constraints to be incorporated easily. We illustrate this on the max-min allocation problem with submodular valuations, submodular maximization subject to a matroid and multiple linear constraints, the crossing spanning tree problem, and resource allocation / broadcast scheduling problems with various demand/capacity constraints.

  • Minimum-Cost Network Design with (Dis)economies of Scale Authors: Matthew Andrews and Spyridon Antonakopoulos and Lisa Zhang
    Given a network, a set of demands and a cost function $f(cdot)$, the min-cost n etwork design problem is to route all demands with the objective of minimizing $ sum_e f(ell_e)$, where $ell_e$ is the total traffic load under the routing. We focus on cost functions of the form $f(x)= sigma + x^{alpha}$ for $x > 0$, with $f(0) = 0$. For $alpha le 1$, $f(cdot)$ is subadditive and exhibits beha vior consistent with economies of scale. This problem corresponds to the well-s tudied Buy-at-Bulk network design problem and admits polylogarithmic approximati on and hardness.

    In this paper, we focus on the less studied scenario of $alpha > 1$ with a posi tive startup cost $sigma > 0$. Now, the cost function $f(cdot)$ is neither sub additive nor superadditive. This is motivated by minimizing network-wide energy consumption when supporting a set of traffic demands. It is commonly accepted that, for some computing and communication devices, doubling processing speed mo re than doubles the energy consumption. Hence, in Economics parlance, such a cos t function reflects emph{diseconomies of scale}.

    We begin by discussing why existing routing techniques such as randomized roundi ng and tree-metric embedding fail to generalize directly. We then present our m ain contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitat ed min-cost flow problem that we believe is interesting in its own right. Our ap proach for this problem builds upon the well-linked decomposition due to Chekuri -Khanna-Shepherd~cite{ChekuriKS05}, the construction of expanders via matchings due to Khandekar-Rao-Vazirani~cite{KhandekarRV06}, and edge-disjoint routing i n well-connected graphs due to Rao-Zhou~cite{RaoZ06}. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.

  • One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk Authors: Ashish Goel and Ian Post
    We study the single-sink buy-at-bulk problem with an unknown cost function. We want to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. We present a simple, fast, deterministic, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 49.48-approximation of the optimal cost for that f. This is within a factor of 2 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time.
  • Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time Authors: Glencora Borradaile and Piotr Sankowski and Christian Wulff-Nilsen
    For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a min $st$-cut in $G$? We show how to answer such queries in constant time with $O(nlog^5n)$ preprocessing time and $O(nlog n)$ space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(nlog^5n)$ time and $O(nlog n)$ space and an explicit representation with additional $O(C)$ time and space where $C$ is the size of the basis.

    These results require that shortest paths be unique. We deterministically remove this assumption with an additional $log^2 n$ factor in the running time.

  • Subcubic Equivalences Between Path, Matrix, and Triangle Problems Authors: Virginia Vassilevska Williams and Ryan Williams
    The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most $w$ into polynomial number of chains -- see Trotter's chapter emph{Partially ordered sets} in the emph{Handbook of Combinatorics}. So far the best known on-line algorithm of Kierstead used at most $(5^w-1)/4$ chains; on the other hand Szemer'{e}di proved that any on-line algorithm requires at least $inom{w+1}{2}$ chains. These results were obtained in the early eighties and since then no progress in the general case has been done.

    We provide an on-line algorithm that partitions orders of width $w$ into at most $w^{16log{w}}$ chains. This yields the first sub-exponential upper bound for on-line chain partitioning problem.

  • Replacement Paths via Fast Matrix Multiplication Authors: Oren Weimann and Raphael Yuster
    Let G = (V, E) be a directed edge-weighted graph and let P be a shortest path from s to t in G. The {em replacement paths} problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem -- removing each edge e on P one at a time and computing the shortest s-to-t path each time -- is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related {em shortest paths} problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths in {-M,...,M}, we give a randomized O(Mn^{1+2omega/3}) = O(Mn^{2.584}) time algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. In particular, it runs in O(n^{1+2omega/3}) time if the weights are small (positive or negative) integers. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.
  • All-Pairs Shortest Paths in O(n2) Time With High Probability Authors: Yuval Peres and Dmitry Sotnikov and Benny Sudakov ad Uri Zwick
    We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random from $[0,1]$ is~$O(n^2)$, in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, again in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(log^{2}n)$ expected time.
  • Approximating Maximum Weight Matching in Near-linear Time Authors: Ran Duan and Seth Pettie
    Given a weighted graph, the {em maximum weight matching} problem (MWM) is to find a set of vertex-disjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in $ ilde{O}(msqrt{n})$ time, where $m$ and $n$ are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing $(1-epsilon)$-approximate MWMs or finding maximum cardinality matchings, are not known to be much easier (on sparse graphs). The best algorithms for these problems also run in $ ilde{O}(msqrt{n})$ time.

    In this paper we present the first near-linear time algorithm for computing $(1-epsilon)$-approximate MWMs. Specifically, given an arbitrary real-weighted graph and $epsilon>0$, our algorithm computes such a matching in $O(mepsilon^{-2}log^3 n)$ time. The previous best approximate MWM algorithm with comparable running time could only guarantee a $(2/3-epsilon)$-approximate solution. In addition, we present a faster algorithm, running in $O(mlog nlogepsilon^{-1})$ time, that computes a $(3/4-epsilon)$-approximate MWM.