We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and such that every edge $e$ belongs to either the graph induced by $A$ or the graph induced by $B$. The goal is to minimize $\max\{|A|,|B|\}$. This is the most simple case of the Channel Allocation problem [R. Gandhi et al., Networks, 47 (2006), pp. 225--236]. A solution that outputs $V,\emptyset$ gives ratio at most 2. We show that under a similar strong Unique Games Conjecture by Bansal and Khot [ Optimal long code test with one free bit, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS'09, IEEE, 2009, pp. 453--462] there is no $2-\epsilon$ ratio algorithm for the problem, for any constant $\epsilon>0$. Given a bipartite graph, Max-Bi-Clique is a problem of finding the largest $k\times k$ complete bipartite subgraph. For the Max-Bi-Clique problem, a constant factor hardness was known under a random 3-SAT hypothesis of Feige [ Relations between average case complexity and approximation complexity, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, 2002, pp. 534--543] and also under the assumption that ${{\sc NP}}\nsubseteq \mathop{\cap}_{\epsilon>0} \mathsf{DTIME}(2^{n^\epsilon})$ [S. Khot, SIAM J. Comput., 36 (2006), pp. 1025--1071]. It was an open problem in [C. Ambühl, M. Mastrolilli, and O. Svensson, SIAM J. Comput., 40 (2011), pp. 567--596] to prove inapproximability of Max-Bi-Clique assuming weaker conjecture. Our result implies a similar hardness result assuming the Strong Unique Games Conjecture. On the algorithmic side, we also give better than 2 approximation for Bi-Covering on numerous special graph classes. In particular, we get 1.876 approximation for chordal graphs, an exact algorithm for interval graphs, $1+o(1)$ for minor free graphs, $2-4\delta/3$ for graphs with minimum degree $\delta n$, $2/(1+\delta^2/8)$ for $\delta$-vertex expander, $8/5$ for split graphs, $2-(6/5)\cdot 1/d$ for graphs with minimum constant degree $d$, etc. Our algorithmic results are quite nontrivial. In achieving these results, we use various known structural results about the graphs combined with the techniques that we develop tailored to getting better than 2 approximation.

We study the following basic problem called Bi-Covering. Given a graph G(V, E), find two (not necessarily disjoint) sets A subseteq V and B subseteq V such that A union B = V and that every edge e belongs to either the graph induced by A or to the graph induced by B. The goal is to minimize max{|A|, |B|}. This is the most simple case of the Channel Allocation problem [Gandhi et al., Networks, 2006]. A solution that outputs V,emptyset gives ratio at most 2. We show that under the similar Strong Unique Game Conjecture by [Bansal-Khot, FOCS, 2009] there is no 2 - epsilon ratio algorithm for the problem, for any constant epsilon > 0. Given a bipartite graph, Max-bi-clique is a problem of finding largest k*k complete bipartite sub graph. For Max-bi-clique problem, a constant factor hardness was known under random 3-SAT hypothesis of Feige [Feige, STOC, 2002] and also under the assumption that NP !subseteq intersection_{epsilon > 0} BPTIME(2^{n^{epsilon}}) [Khot, SIAM J. on Comp., 2011]. It was an open problem in [Ambühl et. al., SIAM J. on Comp., 2011] to prove inapproximability of Max-bi-clique assuming weaker conjecture. Our result implies similar hardness result assuming the Strong Unique Games Conjecture. On the algorithmic side, we also give better than 2 approximation for Bi-Covering on numerous special graph classes. In particular, we get 1.876 approximation for Chordal graphs, exact algorithm for Interval Graphs, 1 + o(1) for Minor Free Graph, 2 - 4*delta/3 for graphs with minimum degree delta*n, 2/(1+delta^2/8) for delta-vertex expander, 8/5 for Split Graphs, 2 - (6/5)*1/d for graphs with minimum constant degree d etc. Our algorithmic results are quite non-trivial. In achieving these results, we use various known structural results about the graphs, combined with the techniques that we develop tailored to getting better than 2 approximation.

We study a variant of the generalized assignment problem ( gap ), which we label all-or-nothing gap ( agap ). We are given a set of items, partitioned into n groups, and a set of m bins. Each item ℓ has size s ℓ > 0, and utility a ℓ j ⩾ 0 if packed in bin j . Each bin can accommodate at most one item from each group; the total size of the items in a bin cannot exceed its capacity. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of agap by pointing out a central application in scheduling advertising campaigns. Our main result is an O (1)-approximation algorithm for agap instances arising in practice, in which each group consists of at most m /2 items. Our algorithm uses a novel reduction of agap to maximizing submodular function subject to a matroid constraint. For agap instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS) , relying on a nontrivial LP relaxation of the problem. We present a (3 + ε)-approximation as well as PTASs for other special cases of agap , where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of agap studied in this paper.

We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function : the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas — Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods.

In the Movement Repairmen (MR) problem, we are given a metric space ( V , d ) along with a set R of k repairmen r 1 , r 2 , …, r k with their start depots s 1 , s 2 , …, s k ∈ V and speeds v 1 , v 2 , …, v k ⩾ 0, respectively, and a set C of m clients c 1 , c 2 , …, c m having start locations s ′ 1 , s ′ 2 , …, s ′ m ∈ V and speeds v ′ 1 , v ′ 2 , …, v ′ m ⩾ 0, respectively. If t is the earliest time a client c j is collocated with any repairman (say, r i ) at a node u , we say that the client is served by r i at u and that its latency is t . The objective in the (S um -MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients’ latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery [Amazon 2010] and USPS gopost [Service 2010]. We give the first O (log n )-approximation algorithm for the S um -MR problem. In order to approximate S um -MR, we formulate an LP for the problem and bound its integrality gap. Our LP has exponentially many variables; therefore, we need a separation oracle for the dual LP. This separation oracle is an instance of the Neighborhood Prize Collecting Steiner Tree (NPCST) problem in which we want to find a tree with weight at most L collecting the maximum profit from the clients by visiting at least one node from their neighborhoods. The NPCST problem, even with the possibility to violate both the tree weight and neighborhood radii, is still very hard to approximate. We deal with this difficulty by using LP with geometrically increasing segments of the timeline, and by giving a tricriteria approximation for the problem. The rounding needs a relatively involved analysis. We give a constant approximation algorithm for S um -MR in Euclidean Space where the speed of the clients differs by a constant factor. We also give a constant approximation for the makespan variant.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s i , an end time t i , a demand d i > 0, and a profit p i > 0. A task, if accepted, requires d i units of “bandwidth” from time s i to t i and accrues a profit of p i . For every time t , we are also specified the available bandwidth c t , and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. We present the first polynomial time O (log n ) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time o ( n ) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called “no-bottleneck” assumption: max i d i ≤ min t c t , or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n . Our result, on the other hand, does not require these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω( n ) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

Generalized matching problems arise in a number of applications, including computational advertising, recommender systems, and trade markets. Consider, for example, the problem of recommending multimedia items (e.g., DVDs) to users such that (1) users are recommended items that they are likely to be interested in, (2) every user gets neither too few nor too many recommendations, and (3) only items available in stock are recommended to users. State-of-the-art matching algorithms fail at coping with large real-world instances, which may involve millions of users and items. We propose the first distributed algorithm for computing near-optimal solutions to large-scale generalized matching problems like the one above. Our algorithm is designed to run on a small cluster of commodity nodes (or in a MapReduce environment), has strong approximation guarantees, and requires only a poly-logarithmic number of passes over the input. In particular, we propose a novel distributed algorithm to approximately solve mixed packing-covering linear programs, which include but are not limited to generalized matching problems. Experiments on real-world and synthetic data suggest that a practical variant of our algorithm scales to very large problem sizes and can be orders of magnitude faster than alternative approaches.

We consider single processor preemptive scheduling with job-dependent setup times. In this model, a job-dependent setup time is incurred when a job is started for the first time, and each time it is restarted after preemption. This model is a common generalization of preemptive scheduling, and actually of non-preemptive scheduling as well. The objective is to minimize the sum of any general non-negative, non-decreasing cost functions of the completion times of the jobs -- this generalizes objectives of minimizing weighted flow time, flow-time squared, tardiness or the number of tardy jobs among many others. Our main result is a randomized polynomial time O(1)-speed O(1)-approximation algorithm for this problem. Without speedup, no polynomial time finite multiplicative approximation is possible unless P=NP. We extend the approach of Bansal et al. (FOCS 2007) of rounding a linear programming relaxation which accounts for costs incurred due to the non-preemptive nature of the schedule. A key new idea used in the rounding is that a point in the intersection polytope of two matroids can be decomposed as a convex combination of incidence vectors of sets that are independent in both matroids. In fact, we use this for the intersection of a partition matroid and a laminar matroid, in which case the decomposition can be found efficiently using network flows. Our approach gives a randomized polynomial time offline O(1)-speed O(1)-approximation algorithm for the broadcast scheduling problem with general cost functions as well.

In this paper, we propose techniques for clustering large-scale "streaming" graphs where the updates to a graph are given in form of a stream of vertex or edge additions and deletions. Our algorithm handles such updates in an online and incremental manner and it can be easily parallel zed. Several previous graph clustering algorithms fall short of handling massive and streaming graphs because they are centralized, they need to know the entire graph beforehand and are not incremental, or they incur an excessive computational overhead. Our algorithm's fundamental building block is called graph reservoir sampling. We maintain a reservoir sample of the edges as the graph changes while satisfying certain desired properties like bounding number of clusters or cluster-sizes. We then declare connected components in the sampled sub graph as clusters of the original graph. Our experiments on real graphs show that our approach not only yields clusterings with very good quality, but also obtains orders of magnitude higher throughput, when compared to offline algorithms.

We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + ϵ) approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements r uv between node pairs u,v . The goal is to find a minimum-cost subgraph H of G that contains r uv edge-disjoint paths for all u,v ∈ V . In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when r uv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity.

We study a very natural local protocol for a file transfer problem. Consider a scenario where several files, which may have varied sizes and get created over a period of time, are to be transferred between pairs of hosts in a distributed environment. Our protocol assumes that while executing the file transfers, an individual host does not use any global knowledge; and simply subdivides its I/O resources equally among all the active file transfers at that host at any point in time. This protocol is motivated by its simplicity of use and its applications to scheduling map-reduce workloads.

We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval. Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.

We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of size at most a given budget and minimize the total edge-weight across the clusters. In the {\em multiway cut} version of the problem, we are also given a subset of vertices called {\em terminals}. No cluster is allowed to contain more than one terminal. Our problem differs from most of the previously studied clustering problems in that the number of clusters is not specified. We first show that the feasibility version of the multiway cut $\GC$ problem, i.e., determining if there exists a clustering with bounded-size clusters satisfying the multiway cut constraint, can be solved in polynomial time. Our algorithm is based on the min-cut subroutine and an uncrossing argument. This result is in contrast with the NP-hardness of the min-max multiway cut problem, considered by Svitkina and Tardos (2004), in which the number of clusters must equal the number of terminals. Our results for the feasibility version also generalize to any symmetric submodular function. We next show that the optimization version of $\GC$ is NP-hard by showing an approximation-preserving reduction from the $\frac 13$-balanced cut problem. Our main result is an $O(\log^2 n)$-approximation to the optimization version of the multiway cut $\GC$ problem violating the budget by an $O(\log n)$ factor, where $n$ denotes the number of vertices. Our algorithm is based on a set-cover-like greedy approach which iteratively computes bounded-size clusters to maximize the number of new vertices covered.

In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf 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 from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very 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. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an {\em uncros\-sable} set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and $2$-connecting a carefully chosen single vertex. To handle large group-sizes, we use a $p$-Steiner tree algorithm to identify the ``correct'' pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.

We present an algorithm for finding an s-sparse vector x that minimizes the square-error ∥y -- Φx∥2 where Φ satisfies the restricted isometry property (RIP), with isometric constant δ2s < 1/3. Our algorithm, called GraDeS (Gradient Descent with Sparsification) iteratively updates x as: [EQUATION]

We develop a framework of distributed and stateless solutions for implicitly given packing linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. This is motivated by multi-commodity flow problems where flows can be split along possibly exponentially many paths.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a profit pi > 0. A task, if accepted, requires di units of “bandwidth” from time si to ti and accrues a profit of pi. For every time t, we are also specified the available bandwidth ct, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called “no-bottleneck” assumption: maxi di ≤ mint ct, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O (log 2 n ) factor in Õ( m + n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ( m + 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.

We develop a framework of distributed and stateless solutions for packing and covering linear programs (LPs), 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 nonzero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets. The most appealing features of our algorithms are their simplicity and polylogarithmic convergence. For the packing LP $\max\{c\cdot x\mid Ax\leq b,$ $x\geq0\}$, the algorithm associates a dual variable $y_i=\exp[\frac{1}{\epsilon}(\frac{A_ix}{b_i}-1)]$ for each constraint i, and each agent j iteratively increases (resp., decreases) $x_j$ multiplicatively if $A_j^\top y$ is too small (resp., large) as compared to $c_j$. Our algorithm, starting from a feasible solution, always maintains feasibility and computes a $(1+\epsilon)$ approximation in $\mathrm{poly}(\frac{\ln(mn\cdot A_{\max})}{\epsilon})$ rounds. Here m and n are number of rows and columns of A, and $A_{\max}$, also known as the “width” of the LP, is the ratio of the maximum and the minimum nonzero values taken by the expression $A_{ij}/(b_ic_j)$ as the pair $i,j$ varies over the matrix. A similar algorithm works for the covering LP $\min\{b\cdot y\mid A^\top y\geq c,$ $y\geq0\}$ as well. While exponential dual variables have been used in several packing/covering linear programming (LP) algorithms before [S. Plotkin, D. Shmoys, and E. Tardos, Math. Oper. Res., 20 (1995), pp. 257–301; Y. Bartal, J. W. Byers, and D. Raz, Proceedings of the IEEE Symposium on Foundations of Computer Science, 1997; N. Garg and J. Könemann, SIAM J. Comput., 37 (2007), pp. 630–652; L. K. Fleischer, SIAM J. Discrete Math., 13 (2000), pp. 505–520; N. E. Young, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2001; C. Koufogiannakis and N. E. Young, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2007], this is the first algorithm which is both stateless and has polylogarithmic convergence. Our algorithms can be thought of as applying distributed gradient descent/ascent on a carefully chosen potential. Our analysis differs from those of previous multiplicative update based algorithms and argues that while the current solution is far away from optimality, the potential function decreases/increases by a significant factor.

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph $G=(V,E)$ with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds $\{a_v,b_v\}_{v\in 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 for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive $O(1)$-approximation guarantee for degree-bounded intersecting/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph G, edge-subsets $\{E_i\}_{i=1}^k$, and nonnegative 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. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent $+1$ approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661–670].

We consider solutions for distributed unsplittable multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. A requirement here is that each commodity routes its entire demand along a single path at any point in time. Assuming that the minimum capacity of any edge is at least polylogarithmic factor larger than the maximum demand of any commodity, we present a greedy distributed randomized algorithm, which with high probability, achieves 1+ε approximation, in O(H · logO(1)) m · (1/ε)0(1)) iterations where H ≤ n is an upper bound on the number edges allowed on any flow-path. No prior results exist for our distributed model.

We design a stateless and distributed solution to the problem of maximum multicommodity flows--route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capacity constraints. Our main contribution is in extending the work of [1,2] to the case where the flow can be routed along possibly exponentially many different paths. Our algorithm, starting from an arbitrary feasible flow, always maintains a feasible flow, and reaches a 1 + ε approximation of maximum benefit value in Õ(n2) rounds.

A fundamental network design problem is the one of Traffic Aggregation or Network Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair, e.g., to support buffered multicast traffic. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of multicast by different users.

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.

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 av, bvv∈ 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 ⌈ av/1-ε ⌉ + 4, out-degrees at most ⌈ bv/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 (3av+4, 3bv+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 bv/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(log1+ε 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 Eii=1k, and non-negative integers bii=1k, find a minimum-cost spanning tree (if it exists) in G that contains at most bi edges from each set Ei. 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.

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|rj| SigmawjFj(weighted flow time), l |rj| SigmaTj(total tardiness), the broadcast version of 1 |rj| SigmawjFj, an O(I)-speed, 1-approximation for l |rj| Sigma U macrj(throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |rj| SigmawjTj(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.

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures.

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other:

We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation, for which most of the previous distributed algorithms apply, has an exponential number of variables, one for each path.

A fundamental network design problem is the one of SteinerNetwork Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of the multicast by different users. As a result of greedy selfish behavior of users in the network design game, the overall quality of the resulting solution is often not as good as the globally optimum solution of the underlying problem. We are therefore interested in the problem of designing distributed cost sharing mechanisms that induce the selfish agents to converge to the near-optimum solutions.

We show that the sparsest cut in graphs can be approximated within O(log2 n) factor in Õ(n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n2). 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(log2 n) (pseudo) approximation algorithm for the edge-separator problem with a similar running time.

We give an efficient, scalable, and simple algorithm for computation of a central path for navigation in closed virtual environments. The algorithm requires less preprocessing and produces paths of high visual fidelity. The algorithm enables computing paths at multiple resolutions. The algorithm is based on a distance from boundary field computed on a hierarchical subdivision of the free space inside the closed 3D object. We also present a progressive version of our algorithm based on a local search strategy thus giving navigable paths in a localized region of interest.

We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem 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 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a 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 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.

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.

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.