Rohit Khandekar

TCS Journal 2012 Journal Article

Approximating fault-tolerant group-Steiner problems

• Rohit Khandekar
• Guy Kortsarz
• Zeev Nutov

In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In Fault-Tolerant Group-Steiner problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e. g. , edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and 2-connecting a single vertex vs. two distinct vertices from each group. The main contributions of our paper include the introduction of general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases.

TCS Journal 2012 Journal Article

The checkpoint problem

• MohammadTaghi Hajiaghayi
• Rohit Khandekar
• Guy Kortsarz
• Julián Mestre

In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source–destination pairs { ( s 1, t 1 ), ( s 2, t 2 ), …, ( s k, t k ) }, and a collection P of paths connecting the ( s i, t i ) pairs. A feasible solution is a multicut E ′, namely, a set of edges whose removal disconnects every source–destination pair. For each p ∈ P we define cp E ′ ( p ) = | p ∩ E ′ |. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p ∈ P cp E ′ ( p ), while in the maximum checkpoint (MCP) problem the goal is to minimize max p ∈ P cp E ′ ( p ). These problems have several natural applications, e. g. , in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O ( log n ) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O ( n log n / opt ) for MCP and a hardness of 2 under the assumption P ≠ NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all s i, t i having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within c n for some constant c > 0, unless P = NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP -hardness of Gabow [H. N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671].

SODA Conference 2009 Conference Paper

A logarithmic approximation for unsplittable flow on line graphs

• Nikhil Bansal 0001
• Zachary Friggstad
• Rohit Khandekar
• Mohammad R. Salavatipour

ICML Conference 2009 Conference Paper

Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property

• Rahul Garg 0001
• Rohit Khandekar

STOC Conference 2008 Conference Paper

Additive guarantees for degree bounded directed network design

• Nikhil Bansal 0001
• Rohit Khandekar
• Viswanath Nagarajan

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity with degree bounds: given a directed graph G=(V,E) with non-negative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds a v , b v v∈ V on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm that for any 0 ≤ ε ≤ 1/2, computes an f-connected subgraph with in-degrees at most ⌈ a v /1-ε ⌉ + 4, out-degrees at most ⌈ b v /1-ε ⌉ + 4, and cost at most 1/ε times the optimum. This includes, as a special case, the minimum-cost degree-bounded arborescence problem. We also obtain similar results for the (more general) class of crossing supermodular requirements. Our result extends and improves the (3a v +4, 3b v +4, 3)-approximation of Lau et al. Setting ε=0, our result gives the first purely additive guarantee for the unweighted versions of these problems. Our algorithm is based on rounding an LP relaxation for the problem. We also prove that the above cost-degree trade-off (even for the degree-bounded arborescence problem) is optimal relative to the natural LP relaxation. For every 0<ε <1, we show an instance where any arborescence with out-degrees at most b v /1-ε + O(1) has cost at least 1-o(1)/ε times the optimal LP value. For the special case of finding a minimum degree arborescence (without costs), we give a stronger +2 additive approximation. This improves on a result of Lau et al. [13] that gives a 2Δ*+2 guarantee, and Klein et al. [11] that gives a (1+ε)Δ*+O(log 1+ε n) bound, where Δ* is the degree of the optimal arborescence. As a corollary of our result, we (almost) settle a conjecture of Bang-Jensen et al. [1] on low-degree arborescences. Our algorithms use the iterative rounding technique of Jain, which was used by Lau et al. and Singh and Lau in the context of degree-bounded network design. It is however non-trivial to extend these techniques to the directed setting without incurring a multiplicative violation in the degree bounds. This is due to the fact that known polyhedral characterization of arborescences has the cut-constraints which, along with degree-constraints, are unsuitable for arguing the existence of integral variables in a basic feasible solution. We overcome this difficulty by enhancing the iterative rounding steps and by means of stronger counting arguments. Our counting technique is quite general, and it also simplifies the proofs of many previous results. We also apply the technique to undirected graphs. We consider the minimum crossing spanning tree problem: given an undirected edge-weighted graph G, edge-subsets E i i=1 k , and non-negative integers b i i=1 k , find a minimum-cost spanning tree (if it exists) in G that contains at most b i edges from each set E i . We obtain a +(r-1) additive approximation for this problem, when each edge lies in at most r sets; this considerably improves the result of Bilo et al. A special case of this problem is degree-bounded minimum spanning tree, and our result gives a substantially easier proof of the recent +1 approximation of Singh and Lau.

SODA Conference 2008 Conference Paper

Fast load balancing via bounded best response

• Baruch Awerbuch
• Yossi Azar
• Rohit Khandekar

STOC Conference 2008 Conference Paper

Stateless distributed gradient descent for positive linear programs

• Baruch Awerbuch
• Rohit Khandekar

We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate "agent" controlling each variable and an agent is allowed to read-off the current values only of those constraints in which it has non-zero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets.

SODA Conference 2007 Conference Paper

Distributed algorithms for multicommodity flow problems via approximate steepest descent framework

• Baruch Awerbuch
• Rohit Khandekar
• Satish Rao

FOCS Conference 2007 Conference Paper

Non-Preemptive Min-Sum Scheduling with Resource Augmentation

• Nikhil Bansal 0001
• Ho-Leung Chan
• Rohit Khandekar
• Kirk Pruhs
• Cliff Stein 0001
• Baruch Schieber

We give the first O(l)-speed O(l) approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(l)-speed O(l)-approximations for the non-preemptive scheduling problems; l|r j | Sigmaw j F j (weighted flow time), l |r j | SigmaT j (total tardiness), the broadcast version of 1 |r j | Sigmaw j F j, an O(I)-speed, 1-approximation for l |r j | Sigma U macr j (throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |r j | Sigmaw j T j (weighted tardiness). Our main contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.

STOC Conference 2006 Conference Paper

Graph partitioning using single commodity flows

• Rohit Khandekar
• Satish Rao
• Umesh V. Vazirani

We show that the sparsest cut in graphs can be approximated within O(log 2 n) factor in Õ(n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n 2 ). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log 2 n) (pseudo) approximation algorithm for the edge-separator problem with a similar running time.

SODA Conference 2005 Conference Paper

Improved approximation for universal facility location

• Naveen Garg 0001
• Rohit Khandekar
• Vinayaka Pandit

FOCS Conference 2002 Conference Paper

Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems

• Naveen Garg 0001
• Rohit Khandekar

We give a fully polynomial time approximation scheme (FPTAS) for the optimum fractional solution to the Steiner forest problem. This can easily be generalized to obtain an FPTAS for a hitting set problem on a collection of clutters. We also identify three other problems on collections of clutters and show how these four problems are related when the clutters have the max-flow min-cut (MFMC) property. Two of these problems which are generalizations of maximum multicommodity flow and maximum concurrent flow have been well studied in the past and this paper is the first attempt at designing efficient algorithms for the other two problems. Our algorithms are very simple to describe and have running times better than those of existing algorithms. For clutters that do not satisfy the MFMC property (e. g. , k-spanner, multicommodity flows, T-cuts, T-joins etc.), our algorithms are the only ones known (other than the generic algorithms for linear programming) for solving these hitting set problems.

STOC Conference 2001 Conference Paper

Local search heuristic for k-median and facility location problems

• Vijay Arya
• Naveen Garg 0001
• Rohit Khandekar
• Adam Meyerson
• Kamesh Munagala
• Vinayaka Pandit

In this paper, we analyze local search heuristics for the k -median and facility location problems. We define the {\em locality gap\/} of a local search procedure as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k -median, we show that local search with swaps has a locality gap of exactly 5. When we permit p facilities to be swapped simultaneously then the locality gap of the local search procedure is exactly 3+2/p . This is the first analysis of local search for k -median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For Uncapacitated facility location, we show that local search, which permits adding, dropping and swapping a facility, has a locality gap of exactly 3. This improves the 5 bound of Korupolu et al. We also consider a capacitated facility location problem where each facilitym has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new operation which opens one or more copies of a facility and drops zero or more facilities. We prove that local search which permits this new operation has a locality gap between 3 and 4.