An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem

We consider a fault tolerant version of the metric facility location problem in which every city, j, is required to be connected to r _j facilities. We give the first non-trivial approximation algorithm for this problem, having an approximation guarantee of 3 · H _k , where k is the maximum requirement and H _k is the kth harmonic number. Our algorithm is along the lines of [2] for the generalized Steiner network problem. It runs in phases, and each phase, using a generalization of the primal–dual algorithm of [5] for the metric facility location problem, reduces the maximum residual requirement by one.     

Approximation algorithms for hierarchical location problems

We formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k-median and facility location problems. Our work yields new insights into hierarchical clustering, a widely used technique in data analysis. For example, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. A key building block of our hierarchical facility location algorithm is a constant-factor approximation algorithm for an “incremental” variant of the facility location problem; the latter algorithm may be of independent interest.     

Partitioning ideal sets

This paper analyzes a class of approximation algorithms for the NP-complete problem [4] of partitioning a given set of positive real numbers into k subsets. Chandra and Wong [2] analyzed one such algorithm (Graham's LPT rule) for the L ₂ metric on the related classic scheduling problem and proved a 25/24 worst case upper bound in the general case. This result was slightly improved by Leung and Wei [9]. The input sets considered in this paper are sets which have a k-partition with equal sum subsets (termed ideal sets); we prove a new tight upper bound of 37/ 36 for the L ₂ norm on such sets for the entire class of algorithms.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α _k times OPT, where α _k is an increasing function of k, with \(\lim _{k\to \infty } \alpha _{k} = 3\). Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5.     

Incremental Medians via Online Bidding

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work of Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance. An incremental algorithm produces a nested sequence of facility sets F ₁⊆F ₂⊆⋅⋅⋅⊆F _n , where |F _k |=k for each k. Such an algorithm is called c -cost-competitive if the cost of each F _k is at most c times the optimum k-median cost. We give improved incremental algorithms for the metric version of this problem: an 8-cost-competitive deterministic algorithm, a 2e≈5.44-cost-competitive randomized algorithm, a (24+ε)-cost-competitive, polynomial-time deterministic algorithm, and a 6e+ε≈16.31-cost-competitive, polynomial-time randomized algorithm. We also consider the competitive ratio with respect to size. An algorithm is s -size-competitive if the cost of each F _k is at most the minimum cost of any set of k facilities, while the size of F _k is at most sk. We show that the optimal size-competitive ratios for this problem, in the deterministic and randomized cases, are 4 and e. For polynomial-time algorithms, we present the first polynomial-time O(log m)-size-approximation algorithm for the offline problem, as well as a polynomial-time O(log m)-size-competitive algorithm for the incremental problem. Our upper bound proofs reduce the incremental medians problem to the following online bidding problem: faced with some unknown threshold T∈ℝ⁺, an algorithm must submit “bids” b∈ℝ⁺ until it submits a bid b≥T, paying the sum of all its bids. We present folklore algorithms for online bidding and prove that they are optimally competitive. We extend some of the above results for incremental medians to approximately metric distance functions and to incremental fractional medians. Finally, we consider a restricted version of the incremental medians problem where k is restricted to one of two given values, for which we give a deterministic algorithm with a nearly optimal cost-competitive ratio. The conference version of this paper appeared in (Chrobak, M., et al. in Lecture Notes in Computer Science, vol. 3887, pp. 311–322, 2006). Research of M. Chrobak supported by NSF Grant CCR-0208856.     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to “disperse” a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

The Performance of greedy algorithms for the on-line steiner tree and related problems

We study the on-line Steiner tree problem on a general metric space. We show that the greedy on-line algorithm isO(log((d/z)s))-competitive, wheres is the number of regular nodes,d is the maximum metric distance between any two revealed nodes, andz is the optimal off-line cost. Our results refine the previous known bound [9] and show that AlgorithmSB of Bartalet al. [3] for the on-line file allocation problem isO(log logN)-competitive on anN-node hypercube or butterfly network. A lower bound of (log((d/z)s)) is shown to hold.We further consider the on-line generalized Steiner problem on a general metric space. We show that a class of lazy and greedy deterministic on-line algorithms areO(k· logk)-competitive and no on-line algorithm is better than (logk)-competitive, wherek is the number of distinct nodes that appear in the request sequence.For the on-line Steiner problem on a directed graph, it is shown that no deterministic on-line algorithm is better thans-competitive and the greedy on-line algorithm iss-competitive.A preliminary version of this paper has appeared in theProceedings of the Workshop on Algorithms and Data Structures, 1993, Montréal. The first author's research was partially supported by NSF Grant CCR-9009753, whilst that of the second author was partially supported by NSF Grant DDM-8909660 and a University Fellowship from the Graduate School, Yale University.     

Decomposition of Polynomials with Respect to the Cyclic Group of Orderm

Given a polynomial solution of a differential equation, its m -ary decomposition, i.e. its decomposition as a sum of m polynomials P^{[ j ]}(x)  = ∑_kα_j,kx^{λ_{j, k}}containing only exponentsλ_{j, k} with λ_{j,k  + 1} − λ_j,k = m, is considered. A general algorithm is proposed in order to build holonomic equations for the m -ary parts P^{[ j ]}(x) starting from the initial one, which, in addition, provides a factorized form of them. Moreover, these differential equations are used to compute expansions of the m -ary parts of a given polynomial in terms of classical orthogonal polynomials. As illustration, binary and ternary decomposition of these classical families are worked out in detail.     

Class Constrained Bin Covering

We study the following variant of the bin covering problem. We are given a set of unit sized items, where each item has a color associated with it. We are given an integer parameter k≥1 and an integer bin size B≥k. The goal is to assign the items (or a subset of the items) into a maximum number of subsets of at least B items each, such that in each such subset the total number of distinct colors of items is at least k. We study both the offline and the online variants of this problem. We first design an optimal polynomial time algorithm for the offline problem. For the online problem we give a lower bound of 1+H _k−1 (where H _k−1 denotes the (k−1)-th harmonic number), and an O(k)-competitive algorithm. Finally, we analyze the performance of the natural heuristic First fit.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

On Hierarchical Diameter-Clustering and the Supplier Problem

Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Edge-Packing in Planar Graphs

Maximum G Edge-Packing (EPack _G ) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K _1,k ). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k -star edge-packing of size at least half the optimal. Received May 1995, and in revised form November 1995, and in final form December 1997.     

Network Design with Edge-Connectivity and Degree Constraints

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.     

Resource scheduling with variable requirements over time

The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given two sequences of vectors A=A ₁,…,A _n and R=R ₁,…,R _m . Sequence A represents resource availability during n time intervals, where each vector A _i has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R _i has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A _i+k−1 ^j ≥R _k ^j , where A _i+k−1 ^j and R _k ^j are the jth elements of vectors A _i+k−1 and R _k , respectively. One application of this problem is I/O scheduling for multimedia presentations. The fastest known algorithm to compute the optimal solution of this problem has computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time: . We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time, our solution is within 5% of the optimal.     

A strongly competitive randomized paging algorithm

Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH _k of optimum. (H _k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.Partial support for D. D. Sleator was provided by DARPA, ARPA Order 4976, Amendment 20, monitored by the Air Force Avionics Laboratory under Contract F33615-87-C-1499, and by the National Science Foundation under Grant CCR-8658139.     

Approximation Algorithms for Access Network Design

Abstract. We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale . A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal—dual approach to obtain a solution whose cost is within O(K ² ) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K) . Both bounds are obtained under weak assumptions on the trunk costs. Our primal—dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12].     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

Parallel Approximation Algorithms by Positive Linear Programming

Several sequential approximation algorithms for combinatorial optimization problems are based on the following paradigm: solve a linear or semidefinite programming relaxation, then use randomized rounding to convert fractional solutions of the relaxation into integer solutions for the original combinatorial problem. We demonstrate that such a paradigm can also yield parallel approximation algorithms by showing how to convert certain linear programming relaxations into essentially equivalent positive linear programming [LN] relaxations that can be near-optimally solved in NC. Building on this technique, and finding some new linear programming relaxations, we develop improved parallel approximation algorithms for Max Sat, Max Directed Cut, and Max k CSP. The Max Sat algorithm essentially matches the best approximation obtainable with sequential algorithms and has a fast sequential version. The Max k CSP algorithm improves even over previous sequential algorithms. We also show a connection between probabilistic proof checking and a restricted version of Max k CSP. This implies that our approximation algorithm for Max k CSP can be used to prove inclusion in P for certain PCP classes. Received November 1996; revised March 1997.