Search

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [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]

Let S denote the convex hull of m full-dimensional ellipsoids in ℝn. Given ∈ > 0 and δ > 0, we study the problems of computing a (1 + ∈)-approximation to the minimum volume covering ellipsoid of S and a (1 + δ)n-rounding of S. We extend the first-order algorithm of Kumar and Yildirim [J. Optim. Theory Appl., 126 (2005), pp. 1-21] that computes an approximation to the minimum volume covering ellipsoid of a finite set of points inℝn, which, in turn, is a modification of Khachiyan's algorithm [L. G. Khachiyan, Math. Oper. Res., 21 (1996), pp. 307-320]. Our algorithm can also compute a (1 + δ)n-rounding of S. For fixed ∈ > 0 and δ > 0, we establish polynomial-time complexity results for the respective problems, each of which is linear in the number of ellipsoids m. In particular, our algorithm can approximate the minimum volume covering ellipsoid of S in asymptotically the same number of iterations as that required by the algorithm of Kumar and Yildirim to approximate the minimum volume covering ellipsoid of a set of m points. The main ingredient in our analysis is the extension of polynomial-time complexity of certain subroutines in the algorithm from a set of points to a set of ellipsoids. As a byproduct, our algorithm returns a finite "core" set X ⊆ S with the property that the minimum volume covering ellipsoid of X provides a good approximation to the minimum volume covering ellipsoid of S. Furthermore, the size of the core set depends only on the dimension n and the approximation parameter ∈, but not on the number of ellipsoids m. We also discuss the extent to which our algorithm can be used to compute an approximate minimum volume covering ellipsoid and an approximate n-rounding of the convex hull of other sets in ℝn. We adopt the real number model of computation in our analysis. [ABSTRACT FROM AUTHOR]

A polynomial time testable characterization of cost matrices associated with a complete digraph on n nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov [U.S.S.R. Comput. Maths. Math. Phys., 21 (1981), pp. 167-174.] obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices, which can be tested in O(n²) time. We also provide analogous results where tours are replaced by Hamiltonian paths. When the cost matrix is skew-symmetric, we provide polynomial time testable characterizations such that the tour costs take three distinct values. Corresponding results for the case of Hamiltonian paths are also given. Using these results, special instances of the asymmetric traveling salesman problem (ATSP) are identified that are solvable in polynomial time and that have improved constant factor approximation schemes. In particular, we observe that the 3/2 performance guarantee of the Christofides algorithm extends to all metric Hamiltonian symmetric matrices. Further, we identify special classes of ATSP for which polynomial ε-approximation algorithms are available for ε ∈ {3/2, 4/3, 4r, 3r;²/2 , 4+δ/3}, where r > ½ and δ ≥ 0 are constants. [ABSTRACT FROM AUTHOR]

Assuming that NP ⊈ ∩ϵ>0 BPTIME(2nϵ), we show that graph min-bisection, dense k-subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. [ABSTRACT FROM AUTHOR]

We propose an approximation algorithm based on the Lagrangian or price-directive decomposition method to compute an ∈ B approximate solution of the mixed fractional packing and covering problem: find x ∈ B such that f(x) ≤ (1+∈)a, g(x) ≥ (1-∈)b, where f(x), g(x) are vectors with M nonnegative convex and concave functions, a and b are M-dimensional nonnegative vectors, and B is a convex set that can be queried by an optimization oracle. We propose an algorithm that needs only O(M ∈ -2 O(M ∈ -1)) iterations or calls to the oracle. The main contribution is that the algorithm solves the general mixed fractional packing and covering problem (in contrast to pure fractional packing and covering problems and to the special mixed packing and covering problem with B = ℝ + N) and runs in time independent of the so-called width of the problem. [ABSTRACT FROM AUTHOR]

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of ‘global’ approximation guarantee, and we explore its consequences in a wide range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue—one not encountered in the traditional design of approximation algorithms—is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of fundamental problems in resource allocation, and on the structure of their feasible solutions. [ABSTRACT FROM AUTHOR]

The Lovász local lemma due to Erdős and Lovász (Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai 11, 1975, pp. 609-627) is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson (Combinatorica, 7 (1987), pp. 365-374) to derive good approximation algorithms for such problems. We use our extension of the local lemma to prove that randomized rounding produces, with nonzero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension/degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan (J. Comput. System Sci., 37 (1988), pp. 130-143), to obtain constructive (algorithmic) versions of our results for covering integer programs. [ABSTRACT FROM AUTHOR]

In the weighted rectangle stabbing problem we are given a grid in ℝ² consisting of columns and rows each having a positive integral weight, and a set of closed axis-parallel rectangles each having a positive integral demand. The rectangles are placed arbitrarily in the grid with the only assumption being that each rectangle is intersected by at least one column or row. The objective is to find a minimum-weight (multi)set of columns and rows of the grid so that for each rectangle the total multiplicity of selected columns and rows stabbing it is at least its demand. A special case of this problem, called the interval stabbing problem, arises when each rectangle is intersected by exactly one row. We describe an algorithm called STAB, which is shown to be a constant-factor approximation algorithm for different variants of this stabbing problem. [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]

Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. [ABSTRACT FROM AUTHOR]

We adapt a method proposed by Nesterov [Math. Program. Ser. A, 103 (2005), pp. 127–152] to design an algorithm that computes ∊-optimal solutions to fractional packing problems by solving O(∊-1√Knln(m)) separable convex quadratic programs, where n is the number of variables, m is the number of constraints, and K is the maximum number of nonzero elements in any constraint. We show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. For the special case of the maximum concurrent flow problem on a graph G = (V,E) with rational capacities and demands, we obtain an algorithm that computes an ∊-optimal flow by solving shortest path problems, i.e., problems in which the number of shortest paths computed grows as O(∊-1 log(∊-1)) in ∊ and polynomially in the size of the problem. In contrast, previous algorithms required ω(∊-2) iterations. We also describe extensions to the maximum multicommodity flow problem, the pure covering problem, and mixed packing-covering problem. [ABSTRACT FROM AUTHOR]

The cut-norm ∥A∥C of a real matrix A = (aij)i∊R,j∊S is the maximum, over all I ⊂ R, J ⊂ S, of the quantity ∣∑i∊I,j∊J aij∣. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and we provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (aij)i∊R,j∊S, two subsets I ⊂ R and J ⊂ S, such that ∣∑i∊I,j∊J aij∣ ≥ ρ∥A∥C, where ρ > 0 is an absolute constant satisfying ρ > 0.56. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck's inequality. We present three known proofs of Grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [J. ACM, 42 (1995), pp. 1115–1145], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case. [ABSTRACT FROM AUTHOR]

We give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial- time approximation scheme based on a novel adaptation of the m-guillotine method. [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]

The input for the radio broadcast problem is an undirected n-vertex graph G and a source node s. The goal is to send a message from s to the rest of the vertices in the minimum number of rounds. In a round, a vertex receives the message only if exactly one of its neighbors transmits. The radio broadcast problem admits an O(log2 n) approximation [I. Chlamtac and O. Weinstein, in Proceedings of the IEEE INFOCOM, 1987, pp. 874-881; D. Kowalski and A. Pelc, in APPROX-RANDOM, Lecture Notes in Comput. Sci. 3122, Springer, Berlin, 2004, pp. 171-182]. In this paper we consider the additive approximation ratio of the problem. We prove that there exists a constant c so that the problem cannot be approximated within an additive term of c log2 n, unless NP ⊆ BTIME(nO(log log n)). [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 propose a simple and natural linear randomized algorithm for the approximate 1-median selection problem in metric spaces. The 1-median of a finite subset S of a metric space is the element of S which minimizes the average distance from the remaining points in S. This problem is extremely important in most applications using clustering of metric spaces, but also in connection with several algorithms in bioinformatics. The only linear approximation algorithm for the 1-median problem, which provably works in any metric space without going through any Euclidean space, has been proposed by Indyk in [Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Atlanta, 1999, pp. 428--432]. However, Indyk's algorithm, which is based on sufficiently large sampling, turns out not to be a practical solution. The same holds true even for its heuristic variants which use samplings of smaller size. The algorithm we propose has a simple and efficient implementation, which performs better than Indyk's algorithm in practice. On the other hand, while the performance of Indyk's algorithm is guaranteed by an approximation factor, in the case of our algorithm we are only able to produce experimental evidence of its precision. Extensive experimentation has been performed on both synthetic and real input datasets. Synthetic datasets were generated with uniform and skewed distributions, using various metrics. Real datasets have been extrapolated from real world official databases available on the web. Successful results of the proposed algorithm are reported for several applications in bioinformatics and various classes of approximate search queries. [ABSTRACT FROM AUTHOR]

Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. [ABSTRACT FROM AUTHOR]

We study directed network design problems with orientation constraints. An orientation constraint on a pair of nodes u and v states that a feasible solution may include at most one of the arcs (u, v) and (v, u). Such constraints arise naturally in many network design problems, since link or edge resources such as fiber can be used to support traffic in one of two possible directions only. Our first result is that the directed network design problem with orientation constraints can be solved in polynomial time in the case where the requirement function $f$ is positively intersecting supermodular. (The case where there are no orientation constraints follows from the work of Frank [Acta Sci. Math. (Szeged), 41 (1979), pp. 63--76].) The second main result of the paper is a 4-approximation algorithm for the minimum cost strongly edge-connected subgraph problem with orientation constraints. Our algorithm shows that the problem of enforcing orientation constraints can be reduced to the minimum cost $2$-edge-connected subgraph problem on undirected graphs. Finally, we study the problem for general crossing supermodular functions and show the following bicriteria approximation result. Let k denote the maximum requirement of any set under the given requirement function f. We give a 2k-approximation algorithm to construct a solution that satisfies a slightly weaker requirement function, namely, f'(S)=max{f (S)-1,0}. [ABSTRACT FROM AUTHOR]

The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic that achieves a best-known approximation ratio of $1 + \frac{\ln 3}{2} \approx 1.55$ for general graphs and best-known approximation ratios of $\approx 1.28$ for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound ($1.5 \cdot$ OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs. [ABSTRACT FROM AUTHOR]

Extending results of Christie and Irving, we examine the action of reversals and transpositions on finite strings over an alphabet of size k. We show that determining reversal, transposition, or signed reversal distance between two strings over a finite alphabet is NP-hard, while for "dense" instances we give a polynomial-time approximation scheme. We also give a number of extremal results, as well as investigating the distance between random strings and the problem of sorting a string over a finite alphabet. [ABSTRACT FROM AUTHOR]

Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected multigraph. They prove the KR algorithm has an approximation ratio < 1.85. We improve this bound to $\le 1+\sqrt{1/e}<1.61$ (for odd k we modify the base case of the KR algorithm). This is the best-known performance bound for a combinatorial approximation algorithm for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known combinatorial performance bound for any fixed value of $k\ge 3$, e.g., for even k the approximation ratio is $\le 1+(1-{1\over k})^{k/2}$. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on multigraphs, running in the time for O (nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies), respectively. This complements the implementation of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] which uses time O ((kn) 2) and is efficient for small k. [ABSTRACT FROM AUTHOR]

In the weighted set-cover problem we are given a set of elements $E=\{ e_1,e_2, \ldots ,e_n \}$ and a collection $\cal F$ of subsets of $E$, where each $S \in \cal F$ has a positive cost $c_{S}$. The problem is to compute a subcollection $SOL$ such that $\bigcup_{S\in SOL}S_j=E$ and its cost $\sum_{S\in SOL}c_S$ is minimized. When $|S|\le k\ \forall S\in\cal F$ we obtain the weighted $k$-set cover problem. It is well known that the greedy algorithm is an $H_k$-approximation algorithm for the weighted $k$ set cover, where $H_k=\sum_{i=1}^k {1 \over i}$ is the $k$th harmonic number, and that this bound is exact for the greedy algorithm for all constant values of $k$. In this paper we give the first improvement on this approximation ratio for all constant values of $k$. This result shows that the greedy algorithm is not the best possible for approximating the weighted set cover problem. Our method is a modification of the greedy algorithm that allows the algorithm to regret. [ABSTRACT FROM AUTHOR]

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs). [ABSTRACT FROM AUTHOR]

We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set{1,..., w}, and given a parameter $0G with a relative error of at most $\eps$. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of $\Omega( dw \varepsilon^{-2} )$ on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time $O(d\eps^{-2}\log \frac{d}\varepsilon)$ the number of connected components of an unweighted graph to within an additive error of $\varepsilon n$. (This becomes $O(\eps^{-2}\log \frac{1}\varepsilon)$ for $d=O(1)$.) The time bound is shown to be tight up to within the $\log \frac{d}\varepsilon$ factor. Our connected-components algorithm picks $O(1/\varepsilon^2)$ vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST. [ABSTRACT FROM AUTHOR]

We study the problem of finding a path between two vertices in finite directed graphs whose independence number is bounded by some constant k. The independence number of a graph is the largest number of vertices that can be picked such that there is no edge between any two of them. The complexity of this problem depends on the exact question we ask: Do we wish only to tell whether a path exists? Do we also wish to construct such a path? Are we required to construct the shortest one? Concerning the first question, we show that the reachability problem is first-order definable for all k and that its succinct version is $\Pi_2^{\mathrm{P}}$-complete for all k. In contrast, the reachability problems for many other types of finite graphs, including dags and trees, are not first-order definable, and their succinct versions are PSPACE-complete. Concerning the second question, we show not only that we can construct paths in logarithmic space, but that there even exists a logspace approximation scheme for this problem. The scheme gets a ratio r > 1 as additional input and outputs a path that is at most r times as long as the shortest path. Concerning the third question, we show that even telling whether the shortest path has a certain length is NL-complete and thus is as difficult as for arbitrary directed graphs. [ABSTRACT FROM AUTHOR]

We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of $2.414+\epsilon$ in $\tilde{O}(n^2/\epsilon)$ time. This also yields a bicriteria approximation tradeoff of $(1+\gamma,1+2/\gamma)$ for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of $1.853$ in $\tilde{O}(n^3)$ time. This is very close to the approximation guarantee of the best known algorithm which is linear programming (LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving $1.728$. We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this. [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]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage-time product. This improves upon the best previous approximation bounds of Even, Naor, Rao, and Schieber [J. ACM, 47 (2000), pp. 585-616] for these problems by a factor of &Ohm;(log log n). We use the lower bound provided by the volume W of a spreading metric for each of the ordering problems above (as defined by Even et al.) in order to find a solution with cost at most a logarithmic factor times W for these problems. We develop a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by &Ohm;(C/log n), ensuring that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 682-690] with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems. [ABSTRACT FROM AUTHOR]

Karger, Motwani, and Sudan [J. ACM, 45 (1998), pp. 246–265] introduced the notion of a vector coloring of a graph. In particular, they showed that every k-colorable graph is also vector k-colorable, and that for constant k, graphs that are vector k-colorable can be colored by roughly Δ1–2/k colors. Here Δ is the maximum degree in the graph and is assumed to be of the order of nδ for some 0 < δ < 1. Their results play a major role in the best approximation algorithms used for coloring and for maximum independent sets. We show that for every positive integer k there are graphs that are vector k-colorable but do not have independent sets significantly larger than n/Δ1–2/k (and hence cannot be colored with significantly fewer than Δ1–2/k colors). For k = O(log n/ log log n) we show vector k-colorable graphs that do not have independent sets of size (log n)c, for some constant c. This shows that the vector chromatic number does not approximate the chromatic number within factors better than n/polylogn. As part of our proof, we analyze “property testing” algorithms that distinguish between graphs that have an independent set of size n/k, and graphs that are “far” from having such an independent set. Our bounds on the sample size improve previous bounds of Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653–750] for this problem. [ABSTRACT FROM AUTHOR]

We present a new algorithm for the preemptive offline scheduling of independent jobs on a system consisting of m identical machines. The jobs can be parallel; that is, they may need the concurrent availability of several machines for their execution. To this end, we introduce a machine model which is based on existing multiprocessors and accounts for the penalty of preemption. After examining the relation between makespan and total weighted completion time costs for the scheduling of parallel jobs, we show that our new algorithm achieves an approximation factor of 2.37 for total weighted completion time scheduling if no preemption penalty is considered. This compares favorably to the thus far best approximation factor of 8.53 for the nonpreemptive case. To finetune the algorithm with respect to different preemption penalties, we use a fairly simple numerical optimization problem. Further, we present an algorithm to transform the preemptive schedule into a nonpreemptive one. This leads to an improved approximation factor of 7.11 for the nonpreemptive weighted completion time scheduling. [ABSTRACT FROM AUTHOR]

This paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. The previous best algorithm of Khuller and Raghavachari [J. Algorithms, 21 (1996), Pr). 434-450] has approximation ratio 5/3. The algorithm of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560] achieves ratio 3/2 for simple graphs. Our approach, based on the close relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enables us to achieve running time O(mα(m, n)). [ABSTRACT FROM AUTHOR]

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of ε-local optimality and show that, for every ε > 0, an ε-local optimum can be identified in time polynomial in the problem size and 1/ε whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a ε-local optimum, a variation of our main algorithm produces a (δ+ ε)-local optimum in time polynomial in the problem size and 1/ε. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

In this work we study the problem of clustering with respect to the diameter and the radius costs: We say that a set X of points in Rd is (k,b)-clusterable with respect to the diameter cost if X can be partitioned into k subsets (clusters) so that the distance between every pair of points in each cluster is at most b. In the case of the radius cost we require that all points that belong to the same cluster be at a distance of at most b for some common central point. Here we approach the problem of clustering from within the framework of property testing. In property testing, the goal is to determine whether a given object has a particular property or whether it should be modified significantly so that it obtains the property. In the context of clustering, testing takes on the following form: The algorithm is given parameters k, b, β ,and ε and it can sample from the set of points X. The goal of the algorithm is to distinguish between the case when X is (k,b)-clusterable and the case when X is ε-far from being (k, (1 +β)b )-clusterable. By ε-far from being (k,(1 +β )b )-clusterable we mean that more than ε · |X| points should be remove from X so that it becomes (k,(1 +β )b )-clusterable. In this work we describe and analyze algorithms that use a sample of size polynomial in k and 1 /ε and independent of |X|. (The dependence on β and on the dimension, d, of the points varies with the different algorithms.) Such algorithms may be especially useful when the set of points X is very large and it may not even be feasible to observe all of it. Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an ε-fraction of the points in X that have optimal (or close to optimal) cost. The benefit of our algorithms is that they construct an implicit representation of such clusterings in time independent of |X|... [ABSTRACT FROM AUTHOR]

We study the approximability of multidimensional generalizations of three classical packing problems: multiprocessor scheduling, bin packing, and the knapsack problem. Specifically, we study the vector scheduling problem, its dual problem, namely, the vector bin packing problem, and a class of packing integer programs. The vector scheduling problem is to schedule n 4-dimensional tasks on m machines such that the maximum load over all dimensions and all machines is minimized. The vector bin packing problem, on the other hand, seeks to minimize the number of bins needed to schedule all n tasks such that the maximum load on any dimension across all bins is bounded by a fixed quantity, say, 1. Such problems naturally arise when scheduling tasks that have multiple resource requirements. Finally, packing integer programs capture a core problem that directly relates to both vector scheduling and vector bin packing, namely, the problem of packing a maximum number of vectors in a single bin of unit height. We obtain a variety of new algorithmic as well as inapproximability results for these three problems. [ABSTRACT FROM AUTHOR]

Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT ≥ LOAD; previous work showed that OPT < 3 LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT = L + O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any &epsiv; > 0, there exists a c > 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+&epsiv;L, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + &epsiv;)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]

In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex- disjoint paths connecting them. We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient 2log 1-&epsiv; n ratio approximation for any fixed &epsiv; > 0, unless N P ⊇ DTIME(npolylog(n)). We show hardness of approximation results for some important special cases of SNDP, and we exhibit the first lower bound on the approximability of the related classical NP-hard problem of augmenting the connectivity of a graph using edges from a given set. [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]

Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system (X, S), where each S &epsiv; S is a subset of X. The output is a coloring x of the sets in S that satisfies the following constraint: for every x &epsiv; X there exists a color i and a unique set S &epsiv; S such that x &epsiv; S and x(S) = i. The goal is to minimize the number of colors used by the coloring x. Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, θ(log n) colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system (X, S), the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set S &epsiv; S contains a point whose color appears only once in S. We show that O(log lXI) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. [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]

Consider two sets of strings, B (bad genes) and G (good genes), as well as two integers db and dg (db ≤ dg). A frequently occurring problem in computational biology (and other fields) is to find a (distinguishing) substring s of length L that distinguishes the bad strings from good strings, i.e., such that for each string si Ε B there exists a length-L substring ti of si with d(s, ti) ≤ db (close to bad strings), and for every substring ui of length L of every string gi Ε G, d(s, ui) ≥ dg (far from good strings). We present a polynomial time approximation scheme to settle the problem; i.e., for any constant ε > 0, the algorithm finds a string s of length L such that for every si Ε B there is a length-L substring ti of si with d(ti, s) ≤ ( 1 + ε)db, and for every substring ui of length L of every gi ε G, d(ui, s) ≥ (1 − ε)dg if a solution to the original pair (db ≤ dg) exists. Since there is a polynomial number of such pairs (db, dg), we can exhaust all the possibilities in polynomial time to find a good approximation required by the corresponding application problems. [ABSTRACT FROM AUTHOR]

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: ˙ An upper bound of 3m - 1 in general, and an upper bound of 2n - 1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P. Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255-2591. A BSP satisfying the upper bounds can be constructed in O(nlogn) time. ˙ A worst-case lower bound of 2n - o(n) in general, and 3nfrac;2 - o(n) if the rectangles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of 4&frac;3 or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees. [ABSTRACT FROM AUTHOR]

The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications, including network multicasting [G. N. Rouskas and I. Baldine, IEEE 1. on Selected Areas in Communication, 15 (1997), pp. 346-3561 and VLSI clock routing [H. Bakoglu, Circuits, Interconnections, and Packaging for VSLI, Addison-Wesley, Reading, MA, 1990, A. B. Kahng and G. Robins, On Optimal Interconnections for VSLI, Kluwer Academic Publishers, Norwell, MA, 1995]. In these applications edge weights represent propagation delays, and a signal generated at the root should be received by multiple recipients located at the leaves (almost) simultaneously. The objective is to find zero- or bounded-skew trees of minimum total weight, since the weight of the tree is directly proportional to the amount of resources (bandwidth and buffers for network multicasting, power and chip area for clock routing in VLSI) that must be allocated to the tree. Charikar et al. in [Proceedings of the Tenth ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 1999, ACM, New York, 1999, pp. 177-1841 have recently proposed the first strongly polynomial algorithms with proven constant approximation factors, 2e&ap; 5.44 and 16.86, for finding minimum weight zero- and bounded-skew trees, respectively. In this paper we introduce a new approach to these problems, based on zero-skew "stretching" of spanning trees, and obtain algorithms with improved approximation factors of 4 and 14. For the case when tree nodes are points in the plane and edge weights are given by the rectilinear metric our algorithms find zero- and bounded-skew trees of length at most 3 and 9 times the optimum. This case is of special interest in VLSI clock routing. An important feature of our algorithms is their practical running time, which is asymptotically the same as the time needed for computing the minimum spanning tree. [ABSTRACT FROM AUTHOR]

We give a 17⁄12-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was 3⁄2 . If the well-known 4⁄3 conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most 4⁄3 times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target. [ABSTRACT FROM AUTHOR]

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G = (V, E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow. [ABSTRACT FROM AUTHOR]

In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone log n model by a factor of O(log n&frac;log log k). No approximation algorithms were known for the general model considered in this paper. [ABSTRACT FROM AUTHOR]