A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs $F$ from a fixed family $\mathcal F$. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs $G$, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [ Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is $\Theta(\log n)$, and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a $47/7\approx6.71$-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs.

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree G = (V, E) with n = |V| nodes, an additional set of edges L called links and a cost vector . The goal is to choose a minimum cost subset S ⊆ L such that G = (V, E ∪ S) is 2-edgeconnected. In the unweighted case, that is, when we have cℓ = 1 for all ℓ ∊ L, the problem is called the tree augmentation problem (TAP). Both problems are known to be APX-hard, and the best known approximation factors are 2 for WTAP by (Frederickson and JáJá, ’81) and for TAP due to (Kortsarz and Nutov, TALG ’16). Adjashvili (SODA ’17) recently presented an ≈ 1.96418 + ε-approximation algorithm for WTAP for the case where all link costs are bounded by a constant. This is the first approximation with a better guarantee than 2 that does not require restrictions on the structure of the tree or the links. In this paper, we improve Adjiashvili's approximation to a + ε-approximation for WTAP under the bounded cost assumption. We achieve this by introducing a strong LP that combines {0, ½}-Chvátal-Gomory cuts for the standard LP for the problem with bundle constraints from Adjiashvili. We show that our LP can be solved efficiently and that it is exact for some instances that arise at the core of Adjiashvili's approach. This results in the improved performance guarantee of + ε, which is asymptotically on par with the result by Kortsarz and Nutov. Our result also is the best-known LP-relative approximation algorithm for TAP.

Graphs with bounded highway dimension were introduced by Abraham et al. [ Proceedings of SODA 2010, pp. 782--793] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph $G=(V,E)$ of constant highway dimension, we show how to randomly compute a weighted graph $H=(V,E')$ that distorts shortest path distances of $G$ by at most a $1+\varepsilon$ factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of $G$. Our probabilistic embedding implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar's [ Proceedings of STOC 2004, pp. 281--290] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several nontrivial ingredients to Talwar's techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.

This issue of SICOMP contains six specially selected papers from STOC 2014, the Forty-Sixth Annual ACM Symposium on the Theory of Computing, which was held May 31 through June 3, 2014, in New York, NY. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough the reviewing process of SICOMP. The program committee for STOC 2014 consisted of Boris Aronov, Moshe Babaioff, Nikhil Bansal, Glencora Borradaile, Mark Braverman, Petros Drineas, Moritz Hardt, Jochen Könemann, Katrina Ligett, Brendan Lucier, Prasad Raghavendra, Ronitt Rubinfeld, Piotr Sankowski, David Shmoys, Adam Smith, Ola Svensson, Mikkel Thorup, Chris Umans, Vinod Vaikuntanathan, Gregory Valiant, Thomas Vidick, and Lisa Zhang. The program chair was David Shmoys. Out of 319 submission, the committee selected 91 papers for presentation. Included in this issue are the following papers: In “Breaking the Minsky--Papert Barrier for Constant-Depth Circuits," Alexander A. Sherstov resolves a collection of open questions in circuit and communication complexity by providing a family of constant-depth AND-OR circuits whose “threshold degree" (that is, the minimum degree of a polynomial whose sign on every input agrees with the circuit's output) approaches $n^{1/2}$, where $n$ is the number of input wires. This essentially matches the known upper bound of $n^{1/2}$ and vastly improves Minsky and Papert's 1969 bound of $\Omega(n^{1/3})$. In “Constant Rank Two-Player Games Are PPAD-Hard," Ruta Mehta studies bimatrix games given by a pair of playoff matrices $A$ and $B$. The author shows that the problem of computing a Nash equilibrium in such a game is PPAD-hard if the rank of $A+B$ is at least 3. It was previously known that Nash equilibria in rank-1 games can be computed efficiently. In “Fingerprinting Codes and the Price of Approximate Differential Privacy," Mark Bun, Jonathan Ullman, and Salil P. Vadhan give the first tight lower bounds for differentially private estimation of high-dimensional statistics.Their lower bound rules out accurate algorithms that satisfy even very weak privacy guarantees. To obtain the lower bound, they show a connection to fingerprinting codes (Boneh and Shaw) and dramatically simplify and generalize Tardos's 2003 construction of such codes. In “Primal Beats Dual on Online Packing LPs in the Random-Order Model," Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking study packing linear programs in an online model where columns are presented to the algorithm in random order. The authors present a $1-O(\sqrt{(\log d)/B})$ competitive algorithm, where $d$ denotes the column sparsity and $B$ is the capacity ratio. This yields a best possible $(1-\epsilon)$-competitive algorithm if $B$ is $\Omega(\frac{\log d}{\epsilon^2})$. In “Faster All-Pairs Shortest Paths Via Circuit Complexity," R. Ryan Williams breaks a long-standing barrier in the running time of the all-pairs shortest-path problem in dense graphs. Among the many techniques he uses for this is a surprising tool from circuit complexity, namely a polynomial approximation to low-depth arithmetic circuits due to Razborov and Smolensky. In “Formulas vs. Circuits for Small Distance Connectivity," Benjamin Rossman provides the first super-polynomial separation in the power of bounded-depth Boolean formulas vs. circuits. The author considers the Distance $k(n)$ Connectivity problem which asks whether two specific nodes in an $n$-node graph are connected through a path of length $k(n)$. The problem is solvable on circuits of depth $O(\log k)$ and size $O(kn^3)$, but solving the problem on formulas of depth $\log(n)/\log\log(n)^O(1)$ requires size $n^{\Omega(k)}$ for all $k(n)\leq \log\log(n)$.

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

In a standard $f$-connectivity network design problem, we are given an undirected graph $G=(V,E)$, a cut-requirement function $f:2^V \rightarrow {\mathbb{N}}$, and non-negative costs $c(e)$ for all $e \in E$. We are then asked to find a minimum-cost vector $x \in {\mathbb{N}}^E$ such that $x(δ(S)) \geq f(S)$ for all $S \subseteq V$. We focus on the class of such problems where $f$ is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the $f$-connectivity problem with general proper functions $f$. Implementing Jain's algorithm, this yields a strongly polynomial time $(2+ε)$-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).

In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403--417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices.

The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph G = (V, E), non-negative costs c(u) and penalties π(u) for each u ∈ V . The goal is to find a tree T that minimizes the total cost of the vertices spanned by T plus the total penalty of vertices not in T. This problem is well-known to be set-cover hard to approximate. Moss and Rabani (STOC'01) presented a primal-dual Lagrangean-multiplier-preserving O(ln |V |)-approximation algorithm for this problem. We show a serious problem with the algorithm, and present a new, fundamentally different primal-dual method achieving the same performance guarantee. Our algorithm introduces several novel features to the primal-dual method that may be of independent interest.

In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. Additionally, we establish structural properties of basic solutions by using uncrossing methods. For quasi-bipartite instances we show that these hypergraphic relaxations have the same value as the well-studied graphic bidirected cut relaxation. We show how to analyze several approximation algorithms relative to the hypergraphic linear programs; one gives an approximation ratio and integrality gap of at most $\sqrt{3} \simeq 1.729$ for the Steiner tree problem when the full components arrive online.

The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case. We take the approach of exploiting problem structure to achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property known as shallow cell complexity (SCC). Roughly speaking, a set cover instance has low SCC if any column-induced submatrix of the corresponding element-set incidence matrix has few distinct rows. By adapting and improving Varadarajan's recent quasi-uniform random sampling method for weighted geometric covering problems, we obtain strong approximation algorithms for a structurally rich class of weighted covering problems with low SCC. We also show how to derandomize our algorithm. Our main result has several immediate consequences. Among them, we settle an open question of Chakrabarty et al. [8] by showing that weighted instances of the capacitated covering problem with underlying network structure have O(1)-approximations. Additionally, our improvements to Varadarajan's sampling framework yield several new results for weighted geometric set cover, hitting set, and dominating set problems. In particular, for weighted covering problems exhibiting linear (or near-linear) union complexity, we obtain approximability results agreeing with those known for the unweighted case. For example, we obtain a constant approximation for the weighted disk cover problem, improving upon the 2O(log* n)-approximation known prior to our work and matching the O(1)-approximation known for the unweighted variant.

Gupta et al. [J. ACM, 54 (2007), article 11] and Gupta, Kumar, and Roughgarden [in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365–372] recently developed an elegant framework for the development of randomized approximation algorithms for rent-or-buy network design problems. The essential building block of this framework is an approximation algorithm for the underlying network design problem that admits a strict cost sharing scheme. Such cost sharing schemes have also proven to be useful in the development of approximation algorithms in the context of two-stage stochastic optimization with recourse. The main contribution of this paper is to show that the Steiner forest problem admits cost shares that are 3-strict and 4-group-strict. As a consequence, we derive surprisingly simple approximation algorithms for the multicommodity rent-or-buy and the multicast rent-or-buy problems with approximation ratios 5 and 6, improving over the previous best approximation ratios of 6.828 and 12.8, respectively. We also show that no approximation ratio better than 4.67 can be achieved using the sample-and-augment framework in combination with the currently best known Steiner forest approximation algorithms. In the context of two-stage stochastic optimization, our result leads to a 6-approximation algorithm for the stochastic Steiner tree problem in the black-box model and a 5-approximation algorithm for the stochastic Steiner forest problem in the independent decision model.

In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a $(2+\epsilon)$-approximate solution which violates the capacity constraints by a factor of $(4+\epsilon)$ in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee.

We consider a game-theoretical variant of the Steiner forest problem in which each player j, out of a set of k players, strives to connect his terminal pair $(s_j, t_j)$ of vertices in an undirected, edge-weighted graph G. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 (1995), pp. 445–456] yields a 2-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem.

In this article, we consider the problem of computing a minimum-weight vertex-cover in an n -node, weighted, undirected graph G = ( V , E ). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O (log n + log Ŵ ) communication rounds, where Ŵ is the average vertex-weight. The previous best algorithm for this problem requires O (log n (log n + log Ŵ )) rounds and it is not fully distributed. For a maximal matching M in G , it is a well-known fact that any vertex-cover in G needs to have at least | M | vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.

This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We present new, faster, and much simpler algorithms for these problems.

In the multicommodity rent-or-buy (MROB) network design problems, we are given a network together with a set of k terminal pairs ( s 1 , t 1 ), …, ( s k , t k . The goal is to provision the network so that a given amount of flow can be shipped between s i and t i for all 1 ≤ i ≤ k simultaneously. In order to provision the network, one can either rent capacity on edges at some cost per unit of flow, or buy them at some larger fixed cost. Bought edges have no incremental, flow-dependent cost. The overall objective is to minimize the total provisioning cost. Recently, Gupta et al. [2003a] presented a 12-approximation for the MROB problem. Their algroithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique had previously been introduced [Gupta et al. 2003b] for the single-sink rent-or-buy network design problem. In this article we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our article is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal et al. [1995]. Our result significantly reduces the gap between the single-sink and multisink case.

In the multi-commodity rent-or-buy network design problem (MRoB) we are given a network together with a set of k terminal pairs R = (s_1, t_1), ..., (s_k, t_k). The goal is to install capacities on the edges of the network so that a prescribed amount of flow fi can be routed between all terminal pairs si and ti simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost.The version of the stochastic Steiner tree problem (SST) considered here is the Steiner tree problem in the model of two-stage stochastic optimization with recourse. In stage one, there is a known probability distribution on subsets of vertices and we can choose to buy a subset of edges at a given cost. In stage two, a subset of vertices T from the prior known distribution is realized, and additional edges can be bought at a possibly higher cost. The objective is to buy a set of edges in stages one and two so that all vertices in T are connected, and the expected cost is minimized.Gupta et al. (FOCS '03) give a randomized scheme for the MRoB problem that was both used subsequently to improve the approximation ratio for this problem, and extended to yield the best approximation algorithm for SST. One building block of this scheme is a good approximation algorithm for Steiner forests.We present a surprisingly simple 5-approximation algorithm for MRoB and 6-approximation for SST, improving on the best previous guarantees of 6.828 and 12.6, and show that no approximation ratio better than 4.67 can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithms. A key component of our approach are cost shares that are 3-strict for the unmodified primal-dual Steiner forest algorithm.

In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G = (V, E), non-negative vertex weightswtv for all vertices v ∈ V, and node-capacities Bv ≥ 1 for all v ∈ V. A feasible solution to a givencapVC instance consists of a vertex cover C ⊆ V. Each edge e ∈ E is assigned to one of its endpoints in C and the number of edges assigned to any vertex v ∈ C is at most Bv. The goal is to minimize the total weight of C. For a parameter ɛ> 0 we give a deterministic, distributed algorithm for thecapVC problem that computes a vertex cover C of weight at most (2+ɛ)·opt whereopt is the weight of a minimumweight feasible solution to the given instance. The number of edges assigned to any node v ∈ C is at most (4 + ɛ) · Bv. The running time of our algorithm is O(log(nW)/ɛ), where n is the number of nodes in the network and W = wtmax/wtmin is the ratio of largest to smallest weight. This result is complemented by a lower-bound saying that any distributed algorithm forcapVC which requires a poly-logarithmic number of rounds is bound to violate the capacity constraints by a factor two. The main feature of the algorithm is that it is derived in a systematic fashion starting from a primal-dual sequential algorithm.

We present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree (MST) problem: Given an undirected graph with nonnegative edge weights and a degree bound B, find a spanning tree of maximum node-degree B and minimum total edge-cost. Our algorithm outputs a tree of maximum degree at most a constant times B and total edge-cost at most a constant times that of a minimum-cost degree-B-bounded spanning tree. While our new algorithm is based on ideas from Lagrangian relaxation, as is our previous work [SIAM J. Comput., 31 (2002), pp. 1783--1793], it does not rely on computing a solution to a linear program. Instead, it uses a repeated application of Kruskal's MST algorithm interleaved with a combinatorial update of approximate Lagrangian node-multipliers maintained by the algorithm. These updates cause subsequent repetitions of the spanning tree algorithm to run for longer and longer times, leading to overall progress and a proof of the performance guarantee. A second useful feature of our algorithm is that it can handle nonuniform degree bounds on the nodes: Given distinct bounds B v for every node $v \in V$, the output tree has degree at most O(B v + log|V|) for every $v \in V$. As before, the cost of the tree is at most a constant times that of a minimum-cost tree obeying all degree bounds.

We present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree problem: Given an undirected graph with nonnegative edge weights and degree bounds Bv > 1 for all vertices v, find a spanning tree T of minimum total edge-cost such that the maximum degree of each node v in T is at most Bv. Our algorithm finds a tree in which the degree of each node v is O(Bv + log n) and the total edge-cost is at most a constant times the cost of any tree that obeys all degree constraints.Our previous algorithm[9] with similar guarantees worked only in the case of uniform degree bounds (i.e. Bv=B for all vertices v). While the new algorithm is based on ideas from Lagrangean relaxation as is our previous work, it does not rely on computing a solution to a linear program. Instead it uses a repeated application of Kruskal's MST algorithm interleaved with a combinatorial update of approximate Lagrangean node-multipliers maintained by the algorithm. These updates cause subsequent repetitions of the spanning tree algorithm to run for longer and longer times, leading to overall progress and a proof of the performance guarantee.

In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer B * , and the goal is to find a minimum-cost spanning tree T with maximum degree at most B * . In an n-node graph, our algorithm finds a spanning tree with maximum degree O(B * +logn) and cost O(opt B * ), where opt B * is the minimum cost of any spanning tree whose maximum degree is at most B * . Our algorithm uses ideas from Lagrangean duality. We show how a set of optimum Lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.

In this paper, we present a new bicriteria approximation algorithm for the degree- bounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function on the edges, and a positive integer B ∗ , and the goal is to find a minimum- cost spanning tree T with maximum degree at most B ∗ .I n ann-node graph, our algorithm finds a spanning tree with maximum degree O(B∗ + log n) and cost O( opt B∗ ), where opt B∗ is the minimum cost of any spanning tree whose maximum degree is at most B ∗ . Our algorithm uses ideas from Lagrangean duality. We show how a set of optimum Lagrangean multipliers yields bounds on both the degree and the cost of the computed solution.

This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for min-cost flow computations in computing maximum concurrent flow and min-cost multicommodity flow; this yields much faster algorithms when the number of commodities is large.

No abstract available.