This is what Wordle thinks of my publication titles.
You may want to check out the DBLP or ACM lists as well.


2008
1. Set Covering with our Eyes Closed
   (with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski and Mohit Singh)
   FOCS 2008
   
   Imagine being given a set of special points ("cell phone towers") on the plane, and fixing a map from each point on the plane ("user location") to one of these towers that is within range (i.e., the tower "covers" the user location). Can you find a fixed mapping, so that given a set of randomly located users in the plane, the number of towers used by this mapping is close to the size of a minimal set of towers required to cover them. The reader will notice that this problem is trying to solve a set cover instance on the average.
   
   In this paper, given an (unweighted) set cover instance, we show that you can associate each element with some set covering it, so that if a random subset S of elements arrives, the expected cost of using the sets associated with elements of S to cover the subset S is only $O(log mn)$ times the expected optimum. We give a similar result for the weighted case, and for the online stochastic model. Results for stochastic online versions of (non-metric) facility location and multicut are also presented. This continues our study on developing online algorithms that do well in the average-case.
   
   
2. How to Complete a Doubling Metric
   (with Kunal Talwar)
   LATIN 2008
   
   Suppose you are given a weighted graph which defines a shortest-path metric space with small doubling dimension. Can you represent this metric space by an unweighted graph of small doubling dimension? Since unweighted graphs are simpler (and easier to design algorithms for), such a representation is of some importance.
   
   However, the simplest idea of subdividing edges to create an unweighted graph may cause the dimension to increase unboundedly. It is also possible to show that representing the metric exactly is not possible. In this paper we show that if you allow the distances to change by a $(1+eps)$ factor, then the dimension can be maintained to within a $O(log 1/eps)$ factor, independent of the size of the underlying graph.
   
   
3. A plant location guide for the unsure
   (with Barbara Anthony, Vineet Goyal and Viswanath Nagarajan)
   SODA 2008
   
   Consider a min-max version of the k-median problem, where we are given m possible demand sets, and the goal is to locate k medians to minimize the cost they incur on the worst of these demand sets. We give a logarithmic approximation for this problem. In fact, we give some general conditions such that if a location problem satisfies these conditions, there is a reverse-greedy algorithm for the min-max version of the problem. Using this, we give algorithms for fault-tolerant and capacitated versions of k-median, as well as the k-tree problem. Finally, we show that stochastic versions of k-center are as hard as dense-k-subgraph.
   
   
4. Ultra-low-dimensional embeddings for doubling metrics
   (with Hubert Chan and Kunal Talwar)
   SODA 2008
   
   We show that any metric space with an "intrinsic" (doubling) dimension of $k$ can be embedded into $O(k log log n)$ dimensional Euclidean space with distortion $O(log n)$; this dimension-distortion tradeoff is near-optimal. The embedding is, in fact, more general, and gives a smooth tradeoff between the dimension of the Euclidean space, and the distortion incurred for the embedding.
   
   
5. Approximating TSP on metrics with bounded global growth
   (with Hubert Chan)
   SODA 2008
   
   Recent work has shown how to approximately solve the Traveling Salesman Problem on abstract metric spaces with small dimension. However, the notions of dimension used are very "local": they expect every local neighborhood to be well-behaved. What if our metric looks a bit more realistic: it has a few dense regions, but is well-behaved on the average? In this paper, we give a "global" notion of dimension that we call the correlation dimension, which generalizes the popular notion of doubling dimension, and give subexponential time algorithms for TSP on metrics with low correlation dimension.
   
   
6. Set connectivity problems in undirected graphs and the directed Steiner network problem
   (with Chandra Chekuri, Guy Even and Danny Segev)
   SODA 2008
   
   The generalized connectivity problem is a generalization of group Steiner tree, where we are given a graph with pairs of node-sets---we want to build a low-cost network so that for each set-pair, there is one vertex in each of the two sets connected by this network. (One can think of this as a Group Steiner Forest Problem.) In this paper, we give a poly-log approximation algorithm for this problem, and use it to give a $sqrt{k}$ approximation for the Directed Steiner Forest problem. We also give an improved approximation for the set-connector problem of Fukunaga and Nagamochi.
   
   
7. Stochastic analyses for online combinatorial optimization problems
   (with Naveen Garg, Stefano Leonardi and Piotr Sankowski)
   SODA 2008
   
   Consider the online Steiner tree problem, where vertices arrive one by one, and we need to maintain a connected tree containing all the vertices thus far: this problem has a $O(log n)$ competitive algorithm, and moreover an adversary can make any (randomized) algorithm perform this bad. However, what if the request sequence is not given by an adversary, but instead is just a sequence of random vertices drawn from the vertex set? Can we do better than $O(log n)$. In this paper, we answer this in the affirmative for both the natural objective functions one may want to consider in this context. We extend these results to some other subadditive problems. Moreover, we give a constant approximation for the a-priori TSP problem, a result that was independently discovered by Shmoys and Talwar.
   
   
8. Extracting Dynamics from Static Cancer Expression Data
   (with Ziv Bar-Joseph)
   ACM/IEEE Transactions on Computational Biology and Bioinformatics, 5(2):172-182, 2008.
   
   
2007
9. Selecting Observations Against Adversarial Objectives
   (with Andreas Krause, Brendan McMahan and Carlos Guestrin)
   NIPS 2007
   
   Given a monotone submodular function f(), if we want to choose a set A of k elements to maximize f(A), it is well-known that the greedy algorithm gives an (1-1/e)-approximation. In this paper, we consider the robust version of this problem: we have m monotone submodular functions f_i, and want to maximize min_i f_i(A). It is easy to see that the greedy algorithm performs quite badly; indeed, we show that it is impossible to obtain any approximation guarantee if we pick at most k elements. On the positive front, we show how to pick a set of $O(k log m)$ elements that achieves the same value as the best set of size k.
   
   We use these results in a variety of contexts: our experimental results compare favorably to previous semidefinite-programming based heuristics.
   
   
10. Pricing Tree Access Networks with Connected Backbones
    (with Vineet Goyal, Stefano Leonardi and R. Ravi)
    ESA 2007
    
    We give a primal-dual algorithm for the Stochastic Steiner tree problem, and extend that to give a group-strategyproof mechanism for the problem as well.
    
    
11. Dial a Ride from k-forest
    (with MohammadTaghi Hajiaghayi, Viswanath Nagarajan and R. Ravi)
    ESA 2007
    
    The k-forest problem is the following: given an instance of Steiner forest, connect at least k of the pairs with the least-cost network. We give an improved $min{sqrt{k}, sqrt{n}}$ approximation for this problem, via two different reductions to the k-MST problem (one of them using the Erdos-Szekeres theorem!)
    
    We then show how this result can be used to give algorithms with similar guarantees for the dial-a-ride problem, where we are given a bus of size k in a metric space, and the goal is to find the minimum-cost tour that takes each person from their source to their destination. We extend our results to cases where transit times over edges depend on how many people are in the vehicle at that time.
    
    
12. An O(log² k)-competitive Algorithm for Metric Bipartite Matching
    (with Nikhil Bansal, Niv Buchbinder and Seffi Naor)
    ESA 2007
    
    Suppose we have a metric space with k servers and clients arriving online, each client must be irrevocably assigned to some server as soon as it arrives. The cost of an assignment of some clients to servers is given by the sum of the distances between the clients and their assigned servers. How can we minimize this value? While deterministic schemes are clearly bad, we improve on a result of Meyerson et al. and show an O(log² k) competitive randomized algorithm for the problem.
    
    If you want to think about this problem, it's useful to first think about the following puzzle (which is the above problem on the uniform metric): Suppose k impatient passengers board an airplane. Unfortunately, the first passenger in line has lost his seating assignment and chooses a random seat, setting off a chain of displaced (and stressed out) passengers. One by one the remaining passengers board the plane, taking their assigned seat if it's still available, a random empty seat otherwise. What is the expected number of displaced passengers?
    
    
13. Stochastic Steiner Tree with Non-Uniform Inflation
    (with MohammadTaghi Hajiaghayi and Amit Kumar)
    APPROX 2007
    
    While the Steiner tree problem has been well studied in the model of two stage stochastic optimization with recourse, with several different solutions and extensions to the multistage case, all these algorithms work only in the case when all the edge-costs increase by a uniform factor. When each edge-cost is allowed to increase by a different factor, nothing was previously known.
    
    We show that this problem admits a poly-logarithmic approximation guarantee; moreover, it is as hard as the cost-distance problem, for which we have a Omega(log log n) hardness. Also, we show that if the inflation is allowed to vary over scenarios, the problem becomes as hard as Label-cover. Finally, we give a new linear-programming relaxation of the multicommodity cost-distance problem.
    
    
14. Infrastructure Leasing Problems
    (with Barbara Anthony)
    IPCO 2007
    
    Consider the following Steiner Tree leasing problem: We are given a graph with a prespecified root, and a sequence of terminal sets such that the j'th set wants to connect to the root on day j. However, instead of obtaining edges for a single day at a time, or for infinitely long, we are allowed to lease edges for various periods: say {a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy?
    
    We give a general approach to solving such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization.
    
    
15. An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
    (with Jochen Könemann, Stefano Leonardi, R. Ravi and Guido Schäfer)
    SODA 2007
    
    We give a new primal-dual 3-approximation algorithm for the prize-collecting Steiner forest problem, and use it to give group-strategyproof mechanisms for the associated game. We also show that it has a poly-logarithmic inefficiency.
    
    
2006
16. Spanners with Slack
    (with Hubert Chan and Michael Dinitz)
    ESA 2006
    
    Continuing our investigation of metric embeddings results when one has to maintain most but not all the distances, we consider the problems of building sparse spanners, distance labeling schemes and distance oracles in the "slack" model of our FOCS 2005 paper. For example, we show how to build graphs with a linear number of edges that maintain all but a constant fraction of the distances to within a constant factor.
    
    
17. Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost
    (with Andreas Krause, Carlos Guestrin and Jon Kleinberg)
    IPSN 2006 best paper award.
    
    How should you place sensors in a metric space to minimize the communication cost and yet achieve a desired level of information. We give approximation algorithms when the information satisfies some locality properties, and show that these placements do well in actual deployments.
    
    
18. Quorum Placement in Networks: Minimizing Network Congestion
    (with Daniel Golovin, Bruce Maggs, Florin Oprea and Michael K. Reiter)
    PODC 2006.
    
    Following up on our PODC 2005 paper, we ask the question of how how should we place a quorum system on the nodes of a network to minimize the network congestion without overloading any of the nodes of the network?
    
    
19. Oblivious Network Design.
    (with MohammadTaghi Hajiaghayi and Harald Räcke.)
    SODA 2006.
    
    Consider the following form of the Steiner Forest problem: for each pair of vertices {u,v} in the network, you have to decide on a single path P_{uv} between u and v. Now an adversary decides the set S of pairs to be connected, and you pay $1 for each edge in the \union_{(u,v) \in S} P_{uv}. How should you choose the paths?
    
    We give an O(log² n)-competitive algorithm for this problem, and for several generalizations including one where the cost incurred on an edge is not $1, but any (unknown) concave function of the number of paths using it. In general, we develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem).
    
    Our techniques also give an O(log² n)-competitive algorithm for the Universal TSP problem. Moreover, the padding arguments of this paper easily imply constructions for maximum-gradient embeddings (a la Mendel and Naor).
    
    
20. Small hop-diameter sparse spanners for doubling metrics.
    (with T-H. Hubert Chan.)
    Discrete & Computational Geometry, 2008.
    SODA 2006.
    
    We show how to find spanners for doubling metrics having linear O(n eps^{-1}) edges, and where each pair of vertices has a path between them of length (1+eps), which contains a "small" number of edges. This small number is given by the inverse Ackermann function. We also give a matching lower bound.
    
    
21. Approximating Unique Games.
    (with Kunal Talwar.)
    SODA 2006.
    
    A unique game is a graph coloring problem with k colors: each edge has a permutation pi_e on the colors, and is satisfied when the colors of its endpoints corresponds to the permutation pi_e. The objective is to minimize the number of unsatisfied edges. We give an O(log n) approximation for this by rounding an LP relaxation of the problem.
    
    
22. Improved Embedding of Graph Metrics into Random Trees.
    (with Kedar Dhamdhere and Harald Räcke.)
    SODA 2006.
    
    H.L. Mencken said "For every complex problem there is an answer - simple, neat, and wrong." We found a bug in our proof of the improvement, and while we are working on fixing it, we would like to withdraw our claim. The best result for embeddings into subtrees remains the Elkin et al. result of $O(log^2 n loglog n)$.
    
    Two notes: the paper sketches another way to obtain $O(log^2 n loglog n)$ using the CKR/FRT approach (which is slightly different from the EEST paper). Also, our algorithm (with different parameters) can still be used to argue a distortion of $O(log^3 n)$.
    
    We show that any graph metric can be embedded into a distribution over its subtrees with expected distortion $O(log^2 n)$, improving upon a recent result of Elkin et al.
    
    
2005
23. Metric Embeddings with Relaxed Guarantees.
    (with Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Jon Kleinberg, Ofer Neiman and Alex Slivkins.)
    FOCS 2005.
    
    We show that every metric can be embedded into constant dimensional L_p space (and into random trees) with constant distortion on all but a constant fraction of the pairs of points. See the paper for more details, and many more results.
    
    
24. Quorum placement in networks to minimize access delays
    (with Bruce Maggs, Florin Oprea and Michael K. Reiter)
    PODC 2005.
    
    Given a quorum system, how should we place it on the nodes of a network so as to minimize communication delays without overloading any of the nodes of the network?
    
    
25. What about Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.
    (with Martin Pál, R. Ravi, Amitabh Sinha)
    APPROX 2005.
    
    The general Boosted Sampling approach of our STOC04 paper on stochastic optimization works for multiple stages, and also when the inflation factors are correlated with the demand sets.
    
    
26. Where's the Winner? Sorting and Max-finding with Metric Costs.
    (with Amit Kumar)
    APPROX 2005.
    
    We are given a set of elements belonging to a total order, with a distance metric defined on them. The cost of comparing two elements $i$ and $j$ is the distance $d(i,j)$ between them. What is the cheapest way to find the maximum element (or sort them)? We give algorithms with logarithmic competitive ratios for general metrics, and O(1)-competitive algorithms for constant dimensional Euclidean spaces.
    
    
27. Stochastic Steiner Trees without a Root
    (with Martin Pál)
    ICALP 2005.
    Journal version combined with that of our FOCS 2003 paper.
    
    We give the first approximation algorithm for the stochastic Steiner tree (in the two-stage stochastic framework with recourse, as in GPRS04 below) without assuming that the tree must contain a given fixed root vertex. As unrooted stochastic Steiner tree happens to generalize (deterministic) Steiner Forest and Multicommodity Rent-or-Buy, a way to the solution lies in strenghtening the strict cost sharing from our earlier MRoB paper.
    
    
28. Approximations for Generalized Sparsest Cut and Embeddings of L₂ into L₁.
    (with Shuchi Chawla and Harald Räcke)
    SODA 2005.
    ACM Transactions on Algorithms, 4(2):?-?, 2008. SODA 2005 special issue.
    
    We embed negative-type metrics into Euclidean space, and hence into L_1 with distortion O(log^3/4 n). This embeddings result shows that the integrality gap of the Semidefinite relaxation for the Sparsest Cut problem with non-uniform demands is strictly better than that of the LP relaxation; in particular, our result implies an O(log^{3/4} n) approximation for the general Sparsest Cut problem, improving on the previous best O(log n) approximation of [LLR95, AR98].
    
    
29. Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces.
    (with Mihai Badoiu, Kedar Dhamdhere, Yuri Rabinovich, Harald Räcke, R. Ravi and Anastasios Sidiropoulos)
    SODA 2005.
    
    We give algorithms that approximate the optimal distortion that can be achieved when we embed unweighted graph metrics into the line (i.e., into 1-dimensional space). In particular, if the optimal distortion achievable is D, then our algorithm achieves a distoriton of O(D^2). We improve this to O(D^{3/2}) for the case of unweighted trees, and also give an O(n^{O(D)}) time algorithm to find the best embedding.
    
    
30. On Hierarchical Routing in Bounded Growth Metrics.
    (with T-H. Hubert Chan, Bruce M. Maggs and Shuheng Zhou)
    SODA 2005.
    Invitation to the Journal of Scheduling regretfully declined.
    
    We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables. We show how to perform (1 + eps)-stretch routing on a metric (X,d) with routing tables of size at most O(\log^2 Diameter(X)) bits. The constant in the above expression goes as (dim/eps)^{dim}, where dim is the doubling dimension of the metric (X,d).
    
    We also give algorithms to construct (1 + eps)-stretch spanners for a metric (X,d) with maximum degree at most $(2 + 1/eps)^{O(dim)}$, matching the results of Das et al. for Euclidean metrics. The proof details for the spanner construction are here.
    
    
31. On the Approximability of Network Design Problems.
    (with Julia Chuzhoy, Joseph (Seffi) Naor and Amitabh Sinha)
    SODA 2005.
    ACM Transactions on Algorithms, 4(2):?-?, 2008. SODA 2005 special issue.
    
    Consider the problem: we are given a bunch of terminals {t_i}, and the terminal t_i wants to send d_i units of traffic to a server s in an undirected graph G = (V,E). However, bandwidth on each edge e in G can only be allocated in integral multiples of some base capacity u_e, and hence, provisioning k u_e bandwidth on edge e incurs a cost of \ceil{k} times the cost of that edge. The objective is a minimum-cost feasible solution.
    We show that this, and some other well-studied single-sink network design problems are hard to approximate to better than \Omega(log log n): these include the Cost-Distance problem, the Priority Steiner problem, and the Fixed-Charge Network Flow problem.
    
    Note:While the paper does not state this explicitly, the natural linear program for Priority Steiner has an integrality gap of \Omega(log n/log log n) using an example similar to that in the paper.
    
    
2004
32. An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
    (with R. Ravi and Amitabh Sinha)
    FOCS 2004.
    Math. of Operations Research 32(2):345-364, May 2007
    
    The paper gives LP-based algorithms for Stochastic Two-Stage Steiner Tree and Network Design Problems. The model here is different from the GPRS STOC'04 paper below in that different scenarios materializing tomorrow may come with different inflation factors, which makes the problem trickier. (Especially so in the network design problem, where there are two inflation factors which may change independently of each other.)
    
    
33. On the Bidirected Relaxation for Multiway Cut.
    (with Chandra Chekuri and Amit Kumar)
    Discrete Applied Mathematics 150(1-3):67--79.
    
    We study a natural bidirected relaxation for the Multiway Cut problem, and show that the integrality gap of this relaxation is at least that of the CKR relaxation on every instance. Open question: is the LP gap strictly better than 2?
    
    
34. Cost-Sharing Mechanisms for Network Design.
    (with Aravind Srinivasan and Éva Tardos)
    APPROX 2004.
    Algorithmica, 50(1):98-119.
    
    We consider a single source network design problem from a game-theoretic perspective, and show how to use a variant of the method from the GKR STOC'03 paper to develop an approximately budget-balanced and group strategyproof cost-sharing method for the problem. The novelty of our approach stems from our obtaining the cost-sharing methods for the rent-or-buy problem by carefully combining cost-shares for the simpler problem Steiner tree problem; we feel that this idea may have wider implications. Our algorithm is conceptually simpler than the previous such cost-sharing methods known.
    
    
35. Boosted Sampling: Approximation Algorithms for Stochastic Optimization.
    (with Martin Pál, R. Ravi, Amitabh Sinha)
    STOC 2004.
    
    We consider the following stochastic problem: today, we can buy some elements (edges, facilities, vertices..) at a low price, knowing only a distribution on the demands. Tomorrow, the demands will materialize, and we may need to buy some more elements, at a much higher price, to serve those demands. If we are given access to the probability distribution on the demands, what set of elements should we buy today? (This falls under the model of Two-stage Stochastic Optimization with Recourse.) We show a simple but powerful framework that gives constant approximation algorithms for a number of stochastic problems, such as Facility Location, Steiner tree or Vertex Cover.
    
    
36. Approximating average distortion for embeddings into the line.
    (with Kedar Dhamdhere and R. Ravi)
    STACS 2004.
    TOCS special issue for STACS '04, 39(1):93--111, Feb 2006.
    
    
2003
37. On the Covering Steiner Problem
    (with Aravind Srinivasan)
    FST&TCS 2003.
    Theory of Computing Vol. 2, 53--64.
    
    The Covering Steiner problem is a common generalization of the k-MST and Group Steiner problems, and can be thought of as Group Steiner with coverage requirements. While many covering problems become easier to approximate as the requirements increase, the Covering Steiner problem remains at least as hard to approximate as the Group Steiner problem. In fact, the best guarantees previously known for the Covering Steiner problem were worse than those for Group Steiner as the requirements became large. In this work, we present an improved approximation algorithm whose guarantee equals the best known guarantee for the Group Steiner problem.
    
    
38. Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
    (with Amit Kumar, Martin Pál and Tim Roughgarden)
    FOCS 2003.
    J. ACM, 54(3), March 2007.
    
    We flesh out a general framework (building on GKR03) to solve "rent-or-buy" type problems; this uses random sampling to reduce the problem to the "buy-only" problem. As an illustration, the paper gives a 8-approximation to the multicommodity rent-or-buy problem by random sampling, buying a Steiner forest on the sampled nodes, and renting other paths in the resulting graph. The general reduction is phrased in terms of strict cost-shares, which is a novel way of dividing the solution cost among the participants.
    A note for the reader:The algorithm we use for Steiner Forest is simply this: run the standard AKR/GW primal-dual algorithm, note the time T(v) when vertex v becomes inactive. Now run the primal-dual algorithm again, but force a vertex to remain active till time 2T(v).
    
    
39. Bounded geometries, fractals, and low-distortion embeddings.
    (with Robert Krauthgamer and James R. Lee)
    FOCS 2003.
    
    A doubling metric is one in which every ball can be covered by O(1) balls of half the radius. We study embeddings of doubling metrics into low-dimensional normed spaces. Some of the more striking results are that every doubling tree metric embeds into a finite-dimensional Euclidean space with constant distortion, and a nearly-optimal quantitative version of Assouad's theorem whose proof relies on the Lovasz local lemma.
    
    
40. Simpler and Better Approximation Algorithms for Network Design.
    (with Amit Kumar and Tim Roughgarden.)
    STOC 2003.
    Journal version combined with that of our FOCS 2003 paper.
    
    We give dirt-simple and easy-to-analyze randomized algorithms that improve the best-known approximation ratios for connected facility location, virtual private network design, and single-sink buy-at-bulk network design.
    
    
41. Tree Based MPLS Routing.
    (with Amit Kumar and Mikkel Thorup.)
    SPAA 2003.
    
    
42. Improved Results for Directed Multicut.
    SODA 2003.
    
    The paper gives an O(\sqrt{n}) approximation guarantee for the directed multicut problem using an extremely simple algorithm (inspired by a paper of Cheriyan, Karloff and Rabani); believe it or not, this is the best known guarantee for this problem.
    
    
43. Counting Inversions in Streams.
    (with Francis Zane.)
    SODA 2003.
    
    Given a stream of n numbers whizzing past you, can you count the number of inversions in the stream with only polylogarithmic space? Recall that an inversion occurs when p appears after q in the stream, but p < q.) The answer is Yes, if approximate answers are fine --- this is done by a reduction to finding approximate quantiles in the streaming model. However, we need a new algorithm for the small quantiles.
    
    
44. Lower bounds for embedding edit distance into normed spaces.
    (with Alexandr Andoni, Michel Deza, Piotr Indyk, and Sofya Raskhodnikova.)
    SODA 2003.
    
    
45. Embedding k-Outerplanar graphs into l₁.
    (with Chandra Chekuri, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair.)
    SODA 2003.
    SIAM Journal on Discrete Math, 20(1):119--136
    Invitation to Journal of Algorithms special issue for SODA '03 regretfully declined.
    
    In further progress towards the conjecture that planar graphs may be embeddable into l₁ with constant distortion, we show that the conjecture holds true for k-outerplanar graphs (which, loosely, are planar graphs with vertices lying in k "shells").
    
    
2002
46. A Constant Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
    (with Amit Kumar and Tim Roughgarden.)
    FOCS 2002.
    
    Given a collection of source-sink pairs, we want to build a network allowing each of these pairs to send one unit of traffic between themselves. However, the cost function on the edges is a Rent-or-Buy one: where one can rent bandwidth at $1 per unit capacity per unit length, or buy bandwidth at $M per unit capacity per unit length. This paper gives the first constant-factor approximation algorithm for the problem via the primal-dual schema.
    
    
47. Exploring the trade-off between label size and stack depth in MPLS routing.
    (with Amit Kumar and Rajeev Rastogi.)
    INFOCOM 2003.
    
    
48. Designing Edge-Failure Resilient Networks.
    (with Chandra Chekuri, Amit Kumar, Joseph (Seffi) Naor, and Danny Raz.)
    IPCO 2002.
    Algorithmica Special Issue on Network Design 43(1-2):17--41, Aug 2005.
    
    Given a primary network, we want to design a (cheap) backup network so that, when an edge fails, the traffic between its end-points can be rerouted using the backup network in a "local" fashion. We give constant-factor approximation algorithms for the problem. We also handle the case of designing both the primary network and its backup network simultaneously; also, the case when the backup network has to be a tree.
    
    
49. Approximation Algorithms for the Unsplittable Flow Problem.
    (with Amit Chakrabarti, Chandra Chekuri, and Amit Kumar.)
    APPROX 2002.
    Algorithmica 47(1):53--78, Jan 2007.
    
    This paper gives the first constant factor approximation algorithm for the unsplittable flow problem on the line and cycle networks, as well as logarithmic approximations for expanders.
    
    
2001
50. Traveling with a Pez Dispenser (or, Routing Issues in MPLS).
    (with Amit Kumar and Rajeev Rastogi.)
    FOCS 2001.
    SICOMP 34(2):453-474, 2005.
    
    In MPLS each packet header is a stack of labels, and each router can only see the top of the stack. How can we get routing protocols with a small number of labels (for small lookup tables) as well as small stack depth (for a small packet header size)?
    
    
51. Sorting and Selection with Structured Costs
    (with Amit Kumar.)
    FOCS 2001.
    
    Given a set of elements of a total order, how can we sort (or do selection) when comparing different elements may have different (non-unit) costs? This paper gives results for the general case, and for the case when the comparison costs have some structure.
    
    
52. Provisioning a Virtual Private Network: A Network Design problem for Multicommodity flows.
    (with Jon Kleinberg, Amit Kumar, Rajeev Rastogi, and Bülent Yener.)
    STOC 2001.
    
    Instead of specifying a traffic matrix indicating the communication between each pair of users, suppose each user merely specifies an upper bound on the communication it is involved in. We show how to design a network which can support all traffic matrices respecting these thresholds. Algorithms are also given for the case when users can specify both ingress and egress thresholds.
    
    
53. Steiner nodes in Trees don't (really) help.
    SODA 2001.
    
    Steiner nodes can be removed from tree metrics with constant distortion. Somewhat surprisingly, this can be used to emulate multicasts using unicasts with constant delay, and to give combinatorial lower bounds for tree embeddings.
    
    
2000
54. Embeddings of Finite Metrics. Ph.D. thesis, University of California, Berkeley. August 2000.
    
    
55. Constant Factor Approximation Algorithms for a Class of Classification Problems.
    (with Éva Tardos).
    STOC 2000.
    
    Given a graph, the metric labeling problem asks for the vertices to be labeled with a given set of labels to minimize the total cost. We give a simple flow based local-search algorithm for metric labeling using the truncated linear metric.
    
    
56. Improved Bandwidth Approximation for Trees and Chordal graphs.
    SODA 2000.
    Journal of Algorithms, 40(1), 24--36, 2001.
    
    A natural and simple randomized algorithm gives the best-known approximation for Bandwidth Minimization on trees and chordal graphs.
    
    
1999
57. Cuts, Trees and l₁ Embeddings.
    (with Ilan Newman, Yuri Rabinovich, and Alistair Sinclair).
    FOCS 1999.
    Combinatorica, 24(2):233-269, April 2004.
    
    We study the problem of embedding metrics into l₁ and show that series-parallel graphs can be embedded with constant distortion (and give two proofs of this fact). We also show that embeddings into l₁ are equivalent to the finding good Sparsest Cuts. Can these techniques be extended to embed all planar graphs, or graphs of constant treewidth with constant distortion?
    
    
58. Embedding Trees into Low Dimensional Euclidean Spaces.
    STOC 1999.
    Discrete & Computational Geometry, 24(1), 106-116, 2000.
    
    Any tree can be embedded into d-dimensional space with O(n^1/(d-1)) distortion. Note that a lower bound on the distortion is \Omega(n^1/d).
    
    
59. An elementary proof of the Johnson Lindenstrauss lemma.
    (with Sanjoy Dasgupta).
    Random Structures & Algorithms, 22(1):60--65, 2002.
    ICSI TR-99-006.
    
    The JL lemma says: Project any n-point subset of Euclidean space onto a random O(log n/x²) dimensional subspace (and scale up distances); interpoint distances are preserved to within (1 + x) distortion (w.h.p.). The paper gives a simple Chernoff-type (large deviations) proof of this lemma.

Last modified: August 14, 2007