Search

In the directed Steiner tree (DST) problem, we are given an n-vertex directed edgeweighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log² k/ log log k)- approximation algorithm for DST that runs in quasi-polynomial time, i.e., in time n poly log(k) . By assuming the projection game conjecture and NP ¢n0<ε<1 ZPTIME(2nε ) and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of Ω (log² k/ log log k) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvo{\ss}, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296]. [ABSTRACT FROM AUTHOR]

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]

The minimum majority problem is as follows: given a matrix $A \in \{-1, 1\}^{m \times n}$, minimize $\sum_{i=1}^n x_i$ subject to $A {x} \geq {1}$ and ${x} \in ({\mathbb Z}^+)^n$. An approximation algorithm that finds a solution with value $O({opt}^2 \log m)$ in ${poly}(m,n,{opt})$ time is known, which can be obtained by rounding a linear programming relaxation. We establish integrality gaps that limit the prospects for improving upon this guarantee through improved rounding and/or the application of Lovász--Schrijver (LS) or Sherali--Adams (SA) tightening of the relaxation. These gaps show that applying LS and SA relaxations cannot improve upon the $O({opt}^2 \log m)$ guarantee by more than a constant factor in polynomial time. [ABSTRACT FROM AUTHOR]

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem. [ABSTRACT FROM AUTHOR]

We introduce reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. An important new feature of this model, distinguishing it from existing robust network flow models, is that no flow can get lost in the network. Our goal is to compute maximum flows under this robustness requirement. We investigate different variants depending on the number of failing links, the capacities available for rerouting, and integrality requirements. While the most general versions of the model turn out to be NP-hard, we devise linear programming (LP) formulations and combinatorial algorithms for important special cases and provide approximation algorithms for the harder variants. [ABSTRACT FROM AUTHOR]

We study a semide finite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [SIAM J. Optim., 19 (2008), pp. 1559{1573] and show that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with n. To obtain this result, we search for feasible solutions within a highly structured class of matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, these solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other TSP relaxations. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik [Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012, pp. 171{199.] for the k-cycle cover problem also has an unbounded integrality gap. [ABSTRACT FROM AUTHOR]

We study the metric s--t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3 -approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebö [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s--t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2 c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

We consider the following single-machine scheduling problem, which is often denoted 1||∑ fj: we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time pj, and there is a nondecreasing, nonnegative cost function fj (Cj) that specifies the cost of finishing j at time Cj; the objective is to minimize ∑j=1n fj (Cj). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any ∈ > 0, a polynomial time (4 + ∈)-approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and the primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no LP relaxation was known to efficiently approximate the problem. In this paper, we present an LP relaxation with a constant integrality gap for the capacitated facility location. We demonstrate that the fundamental theories of multicommodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding. [ABSTRACT FROM AUTHOR]

We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebô [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s-t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/ϵ2) iterations to compute a (1 + ϵ)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ϵ). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ϵ)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games. [ABSTRACT FROM AUTHOR]

We present a 6-approximation algorithm for the minimum-cost κ-node connected spanning subgraph problem, assuming that the number of nodes is at least κ³ (κ - 1) + κ. We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for κ-outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of κ. [ABSTRACT FROM AUTHOR]

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. [ABSTRACT FROM AUTHOR]

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices s and t, two of these problems ask to find an s-t path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex v is the distance from s to v along the path. The third problem that we study is the k-person ATSPP, in which the goal is to find k paths from s to t, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(log n) [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107--118] until the recent result that improves it to O(log n/ log log n) [A. Asadpour et al., "An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem," in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379--389], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107--118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only O(√n). For directed latency, the best previously known approximation algorithm has a guarantee of O(n½+∈) for any constant ε > 0 [V. Nagarajan and R. Ravi, "The directed minimum latency problem," in Proceedings of the 11th APPROX, 2008, pp. 193--206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of O(log n), but whose analysis also upper bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209]. We then pursue a deeper study of this linear program and its variations, which leads to an O(log n)-approximation for the directed latency problem, a significant improvement over previously known results. Our result for k-person ATSPP is an O(k² log n)-approximation that bounds the integrality gap of a linear programming relaxation by the same factor. We are not aware of any previous work on this problem. [ABSTRACT FROM AUTHOR]

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 √3 ≃ 1.729 for the Steiner tree problem when the full components arrive online. [ABSTRACT FROM AUTHOR]

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g., the optimality of (1 - 1/e)-approximation for monotone submodular maximization under a cardinality constraint and the impossibility of (½ + ε)-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone submodular function over the bases of a matroid. A (1/6 - o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k ≥ 2, there is a class of matroids of fractional base packing number v = k/k - 1 such that any algorithm achieving a better than (1 - 1/v) = 1/k -approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a ½(1 - 1/v - o(1))-approximation algorithm assuming fractional base packing number at least v, where v ∈ (1, 2]. We also present an improved 0.309-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of ¼ - ε. For this problem, we obtain a hardness of (½ + ε)-approximation for any fixed ε > 0. [ABSTRACT FROM AUTHOR]

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time pij if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form pij ∈ {pj∞}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5, which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + Ε ≈ 1.9412 + Ε, where Ε > 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as the configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee but is not known to converge in polynomial time. [ABSTRACT FROM AUTHOR]

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages and hence are called multistage stochastic programming problems. Multi stage stochastic programming and, in particular, multi stage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation method, is quite simple and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems. [ABSTRACT FROM AUTHOR]

We present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is 1 + 1/(2k) + O(1/k²). The more precise version of this bound requires k ≥7, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], 1 + 2/(k + 1). The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + O(1/k√k)) versus 2n). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is 1+(21/11)k < 1+1.91/k for any k > 1. This improves the previous ratio 1+2/k [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant c >0, an approximation ratio ≤ 1+c/k implies P = NP. Our approximation ratio extends to the minimumsize Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. [ABSTRACT FROM AUTHOR]

This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle. [ABSTRACT FROM AUTHOR]

We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATE) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-PATH) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-PATH appeared in 2003. The natural linear programming relaxation of POST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2- e)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for PRIZE-COLLECTING STEINER TREE is below 1.9672. [ABSTRACT FROM AUTHOR]

The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set A of n items and set B of m bins (knapsacks) such that each item a ϵ A has a size size(a) and a profit value profit(a), and each bin b ϵ B has a capacity c(b). The goal is to find a subset U ⊂ A of maximum total profit such that U can be packed into B without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit a fully time polynomial time approximation scheme (FPTAS) even if the number m of bins is two. Kellerer gave a polynomial time approximation scheme (PTAS) for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time nO(log(1/ϵ)/ϵ8). In this paper we propose an efficient PTAS (EPTAS) with parameterized running time 2O(log(1/ϵ)/ϵ5). poly(n) + O(m) for MKP. This also solves an open question by Chekuri and Khanna. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least 1/2 that of the value of the fractional solution. This approximation ratio of 1/2 is an improvement over an Ω(1/ log m) ratio of Dobzinski, Nisan, and Schapira [Proceedings of the 37th Annual ACM Symposium on Theory of Computing (Baltimore, MD), ACM, New York, 2005, pp. 610-618]. We also show an approximation ratio of 1 - 1/e when utility functions are fractionally subadditive. A result similar to this last result was previously obtained by Dobzinski and Schapira [Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL), SIAM, Philadelphia, 2006, pp. 1064-1073], but via a different rounding technique that requires the use of a so-called "XOS oracle." The randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players. [ABSTRACT FROM AUTHOR]

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 (sj, tj ) 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is Ω(log² k), where k denotes the number of groups; this holds even for input graphs that are hierarchically well-separated trees, introduced by Bartal [in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184–193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an (Multiple line equation(s) cannot be represented in ASCII text) integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585–594] to show comparable inapproximability results, assuming that NP has no quasi-polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow-based relaxations) that appear to be most difficult to approximate. [ABSTRACT FROM AUTHOR]

We show that any rational convex polytope is polynomial-time representable as a 3-way line-sum transportation polytope of "slim" (r, c, 3) format. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure. We provide a polynomial-time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bitransportation programs. Our construction resolves several standing problems on 3-way transportation polytopes. For example, it demonstrates that, unlike the case of 2-way contingency tables, the range of values an entry can attain in any slim 3-way contingency table with specified 2-margins can contain arbitrary gaps. Our smallest such example has format (6, 4, 3). Our construction provides a powerful automatic tool for studying concrete questions about transportation polytopes and contingency tables. For example, it automatically provides new proofs for some classical results, including a well-known "real-feasible but integer-infeasible" (6, 4, 3)-transportation polytope of M. Vlach, and bitransportation programs where any feasible bitransportation must have an arbitrarily large prescribed denominator. [ABSTRACT FROM AUTHOR]

We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation schemes along with some inapproximability results showing how the approximability of the problem changes in terms of the number of resources. The results are based on linear programming formulations (though with exponentially many variables) and some interesting connections between resource constrained scheduling and (multidimensional, multiplechoice, and cardinality constrained) variants of the classical knapsack problem. In order to prove the results we generalize a method by Grigoriadis et al. for the max-min resource sharing problem to the case with weak approximate block solvers (i.e., with only constant, logarithmic, or even worse approximation ratios). Finally, we present applications of the above results in fractional graph coloring and multiprocessor task scheduling. [ABSTRACT FROM AUTHOR]

In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling n independent tasks on a set of m parallel processors, where the execution time of a task is a function of the subset of processors assigned to the task. For any fixed m, we propose a fully polynomial approximation scheme that for any fixed ε > 0 finds a preemptive schedule of length at most (1 + ε) times the optimum in O(n) time. We also discuss the nonpreemptive variant of the problem, and present for any fixed m a polynomial approximation scheme that computes an approximate solution of any fixed accuracy in linear time. In terms of the running time, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound. [ABSTRACT FROM AUTHOR]

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the $2$-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent. [ABSTRACT FROM AUTHOR]

We consider parallel, identical machine scheduling problems, where the jobs are subject to precedence constraints and release dates, and where the processing times of jobs are governed by independent probability distributions. Our objective is to minimize the expected value of the total weighted completion time. Building upon a linear programming relaxation by Möhring, Schulz, and Uetz [J. ACM, 46 (1999), pp. 924--942] and a delayed list scheduling algorithm by Chekuri et al. [SIAM J. Comput., 31 (2001), pp. 146--166], we derive the first constant-factor approximation algorithms for this model. [ABSTRACT FROM AUTHOR]

The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177]. [ABSTRACT FROM AUTHOR]

We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; a fixed cost fi is incurred if a facility is opened at location i. Furthermore, there is a set of demand locations to be serviced by the opened facilities; if the demand location j is assigned to a facility at location i, then there is an associated service cost proportional to the distance between i and j, cij. The objective is to determine which facilities to open and an assignment of demand points to the opened facilities, so as to minimize the total cost. We assume that the distance function c is symmetric and satisfies the triangle inequality. For this problem we obtain a (1 + 2/ e)-approximation algorithm, where 1 + 2/ e&ap; 1.736, which is a significant improvement on the previously known approximation guarantees. The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. Our techniques use properties of optimal solutions to the linear program, randomized rounding, as well as a generalization of the decomposition techniques of Shmoys, Tardos, and Aardal [Proceedings of the 29th ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 265-274]. [ABSTRACT FROM AUTHOR]

We present a linear programming-based method for finding "gadgets," i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich, and Sudan [SIAM J. Comput., 27 (1998), pp. 804-915] of how to prove the optimality of gadgets: linear programming duality gives such proofs. The new gadgets, when combined with recent results of Håstad [Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1-10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 16/17+ ∊ and 12/13+ ∊ , respectively, is NP-hard for every ∊ > 0. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [SIAM J. Comput., 27 (1998), pp. 804-915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and Håstad is 18/19. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. [ABSTRACT FROM AUTHOR]

Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known. [ABSTRACT FROM AUTHOR]