Arrow Research search

Author name cluster

Chandra Chekuri

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

62 papers
2 author rows

Possible papers

62

NeurIPS Conference 2025 Conference Paper

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

  • Elfarouk Harb
  • Yousef Yassin
  • Chandra Chekuri

We consider the following question: given a submodular or supermodular set function $f: 2^V \to \mathbb{R}$, how should one minimize or maximize its average value $f(S)/|S|$ over non-empty subsets $S\subseteq V$? This problem generalizes several well-known objectives including Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications [39, 31], we formalize two new broad problems: the Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS) which allow negative and non-monotone functions. Using classical results we observe that DSS, SFM, USSS, UDSS, and MNP are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one problem can be repurposed to solve others efficiently. In particular we use the perspective of the minimum norm point in the base polyhedron of a sub/supermodular function which, via Fujishige's results, yields the dense decomposition as a byproduct. Via this perspective we show that a recent converging heuristic for DSS, \textsc{SuperGreedy++} [15, 29], and Wolfe’s minimum norm point algorithm are both universal solvers for all of these problems. On the theoretical front, we explain the observation made in recent work [39, 31] that \textsc{SuperGreedy++} appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including for example that it can act as an effective minimum $st$ cut algorithm. On the empirical front, we explore the utility of several different algorithms including Fujishige-Wolfe min-norm point algorithm for recent problems. We conduct over 400 experiments across seven problem types and large-scale synthetic and real-world datasets (up to $\approx 100$ million edges). Our results reveal that methods historically considered inefficient, such as convex-programming methods, flow-based solvers, and Fujishige-Wolfe’s algorithm, outperform state-of-the-art task-specific baselines by orders of magnitude on concrete problems like HNSN [39]. These findings challenge prevailing assumptions and demonstrate that with the right framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems.

PDF Details

AAAI Conference 2024 Conference Paper

1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

  • Chandra Chekuri
  • Pooja Kulkarni
  • Rucha Kulkarni
  • Ruta Mehta

We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

  • Elfarouk Harb
  • Kent Quanrud
  • Chandra Chekuri

We study the densest subgraph problem (DSG) and the densest subgraph local decomposition problem (DSG-LD) in undirected graphs. We also consider supermodular generalizations of these problems. For large scale graphs simple iterative algorithms perform much better in practice than theoretically fast algorithms based on network-flow or LP solvers. Boob et al [1] recently gave a fast iterative algorithm called Greedy++ for DSG. It was shown in [2] that it converges to a $(1-\epsilon)$ relative approximation to the optimum density in $O(\frac{1}{\epsilon^2} \frac{\Delta(G)}{\lambda^*})$ iterations where $\Delta(G)$ is the maximum degree and $\lambda^*$ is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank-Wolfe algorithm for DSG-LD that takes $O(\frac{m\Delta(G) }{\epsilon^2})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector $\hat{b}$, where $m$ is number of edges in the graph. In this paper we give a new iterative algorithm for both problems that takes at most $O(\frac{\sqrt{m\Delta(G)}}{\epsilon})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector; each iteration can be implemented in $O(m)$ time. We describe a fractional peeling technique which has strong empirical performance as well as theoretical guarantees. The algorithm is scalable and simple, and can be applied to graphs with hundreds of millions of edges. We test our algorithm on real and synthetic data sets and show that it provides a significant benefit over previous algorithms. The algorithm and analysis extends to hypergraphs.

PDF Details

SODA Conference 2021 Conference Paper

Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions

  • Karthekeyan Chandrasekaran
  • Chandra Chekuri

We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric submodular function f: 2 V → ℝ into k non-empty parts V 1, V 2, …, V k to minimize. Our algorithm runs in time, where n = | V | and T is the time to evaluate f on a given set; hence. this yields a polynomial time algorithm for any fixed k in the evaluation oracle model. As an immediate corollary, for any fixed k, there is a polynomial-time algorithm for the problem of partitioning the vertex set of a given hypergraph H = ( V, E ) into k non-empty parts to minimize the maximum capacity of the parts. The complexity of this problem. termed M inmax -H ypergraph - k -P art, was raised by Lawler in 1973 [16]. In contrast to our positive result, the reduction in [6] implies that when k is part of the input, M inmax -H ypergraph - k -P art is hard to approximate to within an almost polynomial factor under the Exponential Time Hypothesis (ETH).

Details

FOCS Conference 2020 Conference Paper

Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time

  • Karthekeyan Chandrasekaran
  • Chandra Chekuri

We consider the Hypergraph- k-Cut problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c: E→ \mathbbR+ and a positive integer k. The objective is to find a least-cost subset F ⊆ E such that the number of connected components in G-F is at least k. An alternative formulation of the objective is to find a partition of V into k non-empty sets V1, V2, .. ., Vk so as to minimize the cost of the hyperedges that cross the partition. Graph- k-Cut, the special case of Hypergraph- k-Cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph- k-Cut when k is fixed, starting with the work of Goldschmidt and Hochbaum (1988) [1], [2]. In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph- k-Cut was developed [3] via a subtle generalization of Karger's random contraction approach for graphs. In this work, we develop the first deterministic polynomial time algorithm for Hypergraph- k-Cut for all fixed k. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in n O(k2 ) time while the second one runs in n O(k) time. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum k-partition by solving minimum ( S, T) -terminal cuts. Our techniques give new insights even for Graph- k-Cut.

Details

SODA Conference 2019 Conference Paper

On Approximating (Sparse) Covering Integer Programs

  • Chandra Chekuri
  • Kent Quanrud

We consider approximation algorithms for covering integer programs of the form min 〈 c, x 〉 over x ∊ ℤ ≥0 n s. t. Ax ≥ b and x ≤ d; where A ∊ ℝ ≥0 m × n, b ∊ ℝ ≥0 m, and c, d ∊ ℝ ≥0 n all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x < d as CIP ∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP ∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP ∞.

Details

STOC Conference 2019 Conference Paper

Parallelizing greedy for submodular set function maximization in matroids and beyond

  • Chandra Chekuri
  • Kent Quanrud

We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized (1 / 2 − є)-approximation in O( log 2 ( n ) / 2 ) rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondrák to obtain a fractional solution that yields a near-optimal randomized ( 1 − 1/ e − є )-approximation in O( log 2 ( n ) / є 3 ) rounds of adaptivity. For non-negative functions we obtain a ( 3−2√2 − є )-approximation and a fractional solution that yields a ( 1 / e − є)-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.

Details

SODA Conference 2019 Conference Paper

Submodular Function Maximization in Parallel via the Multilinear Relaxation

  • Chandra Chekuri
  • Kent Quanrud

Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal (1 – 1/ e – ∊ )-approximation in O (log n / ∊ 2 ) rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints. Formally our problem is to maximize F ( x ) over x ∊ [0, 1] n subject to where F is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal (1 – 1/ e – ∊ )-approximation in O (log 2 m log n / ∊ 4 ) rounds where n is the cardinality of the ground set and m is the number of packing constraints. For many constraints of interest, the resulting fractional solution can be rounded via known randomized rounding schemes that are oblivious to the specific submodular function. We thus derive randomized algorithms with poly-logarithmic adaptivity for a number of constraints including partition and laminar matroids, matchings, knapsack constraints, and their intersections. Our algorithm takes a continuous view point and combines several ideas ranging from the continuous greedy algorithm of [38, 13], its adaptation to the MWU framework for packing constraints [20], and parallel algorithms for packing LPs [31, 41]. For the basic setting of cardinality constraints, this viewpoint gives rise to an alternative, simple to understand algorithm that matches recent results [6, 21]. Our algorithm to solve the multilinear relaxation is deterministic if it is given access to a value oracle for the multilinear extension and its gradient; this is possible in some interesting cases such as the coverage function of an explicitly given set system.

Details

SODA Conference 2018 Conference Paper

Randomized MWU for Positive LPs

  • Chandra Chekuri
  • Kent Quanrud

We describe and analyze a simple randomized multiplicative weight update (MWU) based algorithm for approximately solving positive linear programming problems, in particular, mixed packing and covering LPs. Given m explicit linear packing and covering constraints over n variables specified by N nonzero entries, Young [36] gave a deterministic algorithm returning an (1 + ε )-approximate feasible solution (if a feasible solution exists) in Õ ( N / ε 2 ) time. We show that a simple randomized implementation matches this bound, and that randomization can be further exploited to improve the running time to Õ ( N / ε + m / ε 2 + n / ε 3 ) (both with high probability). For instances that are not very sparse (with at least ῶ(1/ ε ) nonzeroes per column on average), this improves the running time of Õ ( N / ε 2 ). The randomized algorithm also gives improved running times for some implicitly defined problems that arise in combinatorial and geometric optimization.

Details

SODA Conference 2017 Conference Paper

Approximating Multicut and the Demand Graph

  • Chandra Chekuri
  • Vivek Madan

In the minimum Multicut problem, the input is an edge- weighted supply graph G = ( V, E ) and a demand graph H = ( V, F ). Either G and H are directed (Di r -M ül C) or both are undirected (Un dir -M ül C). The goal is to remove a minimum weight set of supply edges E ’ ⊆ E such that in G — E’ there is no path from s to t for any demand edge ( s, t ) ∊ F. Un dir -M ül C admits O (log k )-approximation where k is the number of edges in H while the best known approximation for Di r -M ül C is min{ k, Õ (|V | 11/23 )}. These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In this paper we consider the role that the structure of the demand graph plays in determining the approximability of Multicut. We obtain several new positive and negative results. In undirected graphs our main result is a 2- approximation in n O (t) time when the demand graph excludes an induced matching of size t. This gives a constant factor approximation for a specific demand graph that motivated this work, and is based on a reduction to uniform metric labeling and not via the flow-cut gap. In contrast to the positive result for undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. We prove that, assuming the Unique Games Conjecture (UGC), that for a large class of fixed demand graphs Di r -M ül C cannot be approximated to a factor better than the worst- case flow-cut gap. As a consequence we prove that for any fixed k, assuming UGC, Di r -M ül C with k demand pairs is hard to approximate to within a factor better than k. On the positive side, we obtain a k approximation when the demand graph excludes certain graphs as an induced subgraph. This generalizes the known 2 approximation for directed Multiway Cut to a larger class of demand graphs.

Details

FOCS Conference 2017 Conference Paper

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

  • Chandra Chekuri
  • Kent Quanrud

We give a nearly linear-time randomized approximation scheme for the Held-Karp bound [22] for Metric-TSP. Formally, given an undirected edge-weighted graph G = (V, ε) on m edges and ε > 0, the algorithm outputs in O(m log 4 n/ε 2 ) time, with high probability, a (1 + ε)-approximation to the Held-Karp bound on the Metric-TSP instance induced by the shortest path metric on G. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the O(m 2 log 2 (m)/ε 2 ) running time achieved previously by Garg and Khandekar.

Details

SODA Conference 2017 Conference Paper

Computing minimum cuts in hypergraphs

  • Chandra Chekuri
  • Chao Xu 0002

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H = ( V, E ) with n = │V│, m = |E| and p = Σ e∊E l e l the fastest known algorithm to compute a global minimum cut in H runs in O ( np ) time for the uncapacitated case, and in O ( np + n 2 log n ) time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph H and an integer k we describe an algorithm that runs in O (p) time to find a subhypergraph H ’ with sum of degrees O ( kn ) that preserves all edge-connectivities up to k (a k -sparsifier). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O ( p + Λ n 2 ) time algorithm for computing a global minimum cut of H where λ is the minimum cut value. We generalize Matula's argument for graphs to hy- pergraphs and obtain a (2 + ∊ )-approximation to the global minimum cut in a capacitated hypergraph in time, and in in O ( p / ∊ ) time for uncapacitated hypergraphs. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O ( np + n 2 log n ) time and O (p) space. Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.

Details

SODA Conference 2017 Conference Paper

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems

  • Chandra Chekuri
  • Kent Quanrud

We consider several implicit fractional packing problems and obtain faster implementations of approximation schemes based on multiplicative-weight updates. This leads to new algorithms with near-linear running times for some fundamental problems in combinatorial optimization. We highlight two concrete applications. The first is to find the maximum fractional packing of spanning trees in a capacitated graph; we obtain a (1 - ∊)-approximation in Õ (m/∊ 2 ) time, where m is the number of edges in the graph. Second, we consider the LP relaxation of the weighted unsplittable flow problem on a path and obtain a (1 - ∊)-approximation in O ( n /∊ 2 ) time, where n is the number of demands.

Details

SODA Conference 2016 Conference Paper

A Fast Approximation for Maximum Weight Matroid Intersection

  • Chandra Chekuri
  • Kent Quanrud

We present an approximation algorithm for the maximum weight matroid intersection problem in the independence oracle model. Given two matroids defined over a common ground set N of n elements, let k be the rank of the matroid intersection and let Q denote the cost of an independence query for either matroid. An exact algorithm for finding a maximum cardinality independent set (the unweighted case), due to Cunningham, runs in O ( nk 1. 5 Q ) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O ( nk 2 Q ) time. There are also scaling based algorithms that run in time, where W is the maximum weight (assuming all weights are integers), and ellipsoid-style algorithms that run in O (( n 2 log( n )Q + n 3 polylog( n ))log( nW )) time. Recently, Huang, Kakimura, and Kamiyama described an algorithm that gives a (1 – ∊)-approximation for the weighted matroid intersection problem in O ( nk 1. 5 log( k ) Q /∊) time. We observe that a (1 – ∊)-approximation for the maximum cardinality case can be obtained in O ( nkQ /∊) time by terminating Cunningham's algorithm early. Our main contribution is a (1 – ∊) approximation algorithm for the weighted matroid intersection problem with running time O ( nk log 2 (1/∊) Q /∊ 2 ).

Details

SODA Conference 2016 Conference Paper

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation

  • Chandra Chekuri
  • Vivek Madan

We consider subset feedback edge and vertex set problems in undirected graphs. The input to these problems is an undirected graph G = ( V, E ) and a set S = { s 1, s 2, …, s k } ⊂ V of k terminals. A cycle in G is interesting if it contains a terminal. In the Subset Feedback Edge Set problem (S ubset -FES) the input graph is edge-weighted and the goal is to remove a minimum weight set of edges such that no interesting cycle remains. In the Subset Feedback Vertex Set problem (S ubset -FVS) the input graph is node-weighted and the goal is to remove a minimum weight set of nodes such that no interesting cycle remains. A 2-approximation is known for S ubset -FES [12] and a 8-approximation is known for S ubset -FVS [13]. The algorithm and analysis for S ubset -FVS is complicated. One reason for the difficulty in addressing feedback set problems in undirected graphs has been the lack of LP relaxations with constant factor integrality gaps; the natural LP has an integrality gap of ⊝(log n ). In this paper, we introduce new LP relaxations for S ubset -FES and S ubset -FVS and show that their integrality gap is at most 13. Our LP formulation and rounding are simple although the analysis is non-obvious.

Details

SODA Conference 2016 Conference Paper

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

  • Chandra Chekuri
  • Vivek Madan

We study the multiway cut problem in directed graphs and one of its special cases, the node-weighted multiway cut problem in undirected graphs. In D irected M ultiway C ut (D ir -MC) the input is an edge-weighted directed graph G = ( V, E ) and a set of k terminal nodes { s 1, s 2, …, s k } ⊆ V; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from s i to s j for any i ≠ j. In N ode - weighted M ultiway C ut (N ode - wt -MC) the input is a node-weighted undirected graph G and a set of k terminal nodes { s 1, s 2, …, s k } ⊆ V; the goal is to find a min-weight subset of nodes whose removal ensures that there is no path from s i to s j for any i ≠ j. D ir -MC admits a 2-approximation [28] and N ode - wt -MC admits a -approximation [21], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an optimum solution to an LP relaxation. This is particularly true for D ir -MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [28]. In this paper we describe extremely simple and near linear-time rounding algorithms for D ir -MC and N ode - wt -MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with any feasible solution to the relaxation. Consequently, in addition to obtaining “book” proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for D ir -MC when k = 2 and prove that the integrality gap of the LP relaxation is 2 even in planar directed graphs.

Details

SODA Conference 2015 Conference Paper

Degree-3 Treewidth Sparsifiers

  • Chandra Chekuri
  • Julia Chuzhoy

We study treewidth sparsifiers. Informally, given a graph G of treewidth k, a treewidth sparsifier H is a minor of G, whose treewidth is close to k, |V ( H )| is small, and the maximum vertex degree in H is bounded. Treewidth sparsifiers of degree 3 are of particular interest, as routing on node-disjoint paths, and computing minors seems easier in sub-cubic graphs than in general graphs. In this paper we describe an algorithm that, given a graph G of treewidth k, computes a topological minor H of G such that (i) the treewidth of H is Ω( k /polylog(k)); (ii) | V ( H )| = O ( k 4 ); and (iii) the maximum vertex degree in H is 3. The running time of the algorithm is polynomial in | V ( G )| and k. Our result is in contrast to the known fact that unless NP ⊆ coNP/poly, treewidth does not admit polynomial-size kernels. One of our key technical tools, which is of independent interest, is a construction of a small minor that preserves node-disjoint routability between two pairs of vertex subsets. This is closely related to the open question of computing small good-quality vertex-cut sparsifiers that are also minors of the original graph.

Details

FOCS Conference 2013 Conference Paper

Approximation Algorithms for Euler Genus and Related Problems

  • Chandra Chekuri
  • Anastasios Sidiropoulos

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(√n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomialtime algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g O(1) · log O(1) n. Combined with the upper bound from [3], our result also implies a O(n 1/2-α )-approximation, for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT O(1) · log O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

Details

FOCS Conference 2011 Conference Paper

Approximation Algorithms for Submodular Multiway Partition

  • Chandra Chekuri
  • Alina Ene

We study algorithms for the SUBMODULAR Multiway PARTITION problem (SUB-MP). An instance of SUB-MP consists of a finite ground set V, a subset S = {s 1, S 2, .. ., s k } ⊆ V of k elements called terminals, and a non-negative submodular set function f: 2 V → ℝ + on V provided as a value oracle. The goal is to partition V into k sets A 1, .. ., A k to minimize Σ i=1 k f(A i ) such that for 1 ≤ i ≤ k, s i ∈ A i. SUB-MP generalizes some well-known problems such as the MULTIWAY CUT problem in graphs and hypergraphs, and the NODE-WEIGHED MULTIWAY Cut problem in graphs. SUB-MP for arbitrary sub- modular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki [29]. Previous algorithms were based on greedy splitting and divide and conquer strategies. In recent work [5] we proposed a convex-programming relaxation for SUB-MP based on the Lovasz-extension of a submodular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary submodular functions via this relaxation. (1) A 2-approximation for SUB-MP. This improves the (k - 1)-approximation from [29]. (2) A (1. 5 - 1/k)-approximation for SUB-MP when f is symmetric. This improves the 2(1 - 1/k)-approximation from [23], [29].

Details

SODA Conference 2011 Conference Paper

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding

  • Chandra Chekuri
  • Jan Vondrák
  • Rico Zenklusen

Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution x in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point x can be rounded to a random solution R such that E [1 R ] = (1 − δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on S and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].

Details

FOCS Conference 2010 Conference Paper

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

  • Chandra Chekuri
  • Jan Vondrák
  • Rico Zenklusen

We consider the problem of randomly rounding a fractional solution x in an integer polytope P ⊆ [0, 1] n to a vertex X of P, so that E[X] = x. Our goal is to achieve 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 poly topes: the assignment poly tope (that is, bipartite matchings and 6-matchings) [32], [19], [23], and more recently for the spanning tree poly tope [2]. These schemes have led to a number of new algorithmic results. In this paper we describe a new swap rounding technique which can be applied in a variety of settings including matroids and matroid intersection, 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 a martingale argument to obtain an exponential tail estimate for monotone submodular functions. The rounding scheme explicitly exploits exchange properties of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications [19], [23], [7], [22], [2] as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper.

Details

FOCS Conference 2007 Conference Paper

Buy-at-Bulk Network Design with Protection

  • Spyridon Antonakopoulos
  • Chandra Chekuri
  • F. Bruce Shepherd
  • Lisa Zhang 0001

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures, is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case, and an {\rm O}(\log ^3 n) approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

Details

FOCS Conference 2006 Conference Paper

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design

  • Chandra Chekuri
  • MohammadTaghi Hajiaghayi
  • Guy Kortsarz
  • Mohammad R. Salavatipour

We consider approximation algorithms for non-uniform buy-at-bulk network design problems. The first non-trivial approximation algorithm for this problem is due to Charikar and Karagiozova (STOC 05); for an instance on h pairs their algorithm has an approximation guarantee of exp(O(radic(log h log log h)))for the uniform-demand case, and log D middot exp(O(radic(log h log log h))) for the general demand case, where D is the total demand. We improve upon this result, by presenting the first poly-logarithmic approximation for this problem. The ratio we obtain is O(log 3 h middot min{log D, gamma(h 2 )}) where his the number of pairs and gamma(n) is the worst case distortion in embedding the metric induced by a n vertex graph into a distribution over its spanning trees. Using the best known upper bound on gamma(n) we obtain an O(min{log 3 h middot log D, log 5 h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the single-source problem that we need for the multicommodity problem

Details

FOCS Conference 2005 Conference Paper

A Recursive Greedy Algorithm for Walks in Directed Graphs

  • Chandra Chekuri
  • Martin Pál

Given an arc-weighted directed graph G = (V, A, /spl lscr/) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, N et al. (2004)] is O(log/sup 2/ OPT). The second application is an O(log/sup 2/ k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log/sup 2/ k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, N et al.) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than /spl Omega/(log/sup 1-/spl epsi// OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.

Details

FOCS Conference 2004 Conference Paper

Edge-Disjoint Paths in Planar Graphs

  • Chandra Chekuri
  • Sanjeev Khanna
  • F. Bruce Shepherd

We study the maximum edge-disjoint paths problem (MEDP). We are given a graph G = (V, E) and a set T = {s/sub 1/t/sup 1/, s/sub 2/t/sup 2/, .. ., s/sub k/t/sup k/} of pairs of vertices: the objective is to find the maximum number of pairs in T that can be connected via edge-disjoint paths. Our main result is a poly-logarithmic approximation for MEDP on undirected planar graphs if a congestion of 2 is allowed, that is, we allow up to 2 paths to share an edge. Prior to our work, for any constant congestion, only a polynomial-factor approximation was known for planar graphs although much stronger results are known for some special cases such as grids and grid-like graphs. We note that the natural multi-commodity flow relaxation of the problem has an integrality gap of /spl Omega/(/spl radic/|V|) even on planar graphs when no congestion is allowed. Our starting point is the same relaxation and our result implies that the integrality gap shrinks to a poly-logarithmic factor once 2 paths are allowed per edge. Our result also extends to the unsplittable flow problem and the maximum integer multicommodity flow problem. A set X /spl sube/V is well-linked if for each S /spl sub/ V, |/spl delta/(S)| /spl ges/ min{|S /spl cap/ X |, |(V - S) /spl cap/ X|}. The heart of our approach is to show that in any undirected planar graph, given any matching M on a well-linked set X, we can route /spl Omega/(|M|) pairs in M with a congestion of 2. Moreover, all pairs in M can be routed with constant congestion for a sufficiently large constant. This results also yields a different proof of a theorem of Klein, Plotkin, and Rao that shows an O(1) maxflow-mincut gap for uniform multicommodity flow instances in planar graphs. The framework developed in this paper applies to general graphs as well. If a certain graph theoretic conjecture is true, it yields poly-logarithmic integrality gap for MEDP with constant congestion.

Details

STOC Conference 2004 Conference Paper

Multi-processor scheduling to minimize flow time with epsilon resource augmentation

  • Chandra Chekuri
  • Ashish Goel
  • Sanjeev Khanna
  • Amit Kumar 0001

We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their L p norms, for any fixed p ≥ 1.

Details

FOCS Conference 1999 Conference Paper

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

  • Foto N. Afrati
  • Evripidis Bampis
  • Chandra Chekuri
  • David R. Karger
  • Claire Mathieu
  • Sanjeev Khanna
  • Ioannis Milis
  • Maurice Queyranne

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

Details

FOCS Conference 1998 Conference Paper

Approximating a Finite Metric by a Small Number of Tree Metrics

  • Moses Charikar
  • Chandra Chekuri
  • Ashish Goel
  • Sudipto Guha
  • Serge A. Plotkin

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Details