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.     

An Approximation Algorithm for a Large-Scale Facility Location Problem

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy—Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in ( O (3n + 2n log n ) ) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9%-11%, that the Interchange heuristic improved the total cost by an additional 0.5%—1.5%, and that Balloon Search improved it by a further 0.5%—1.5%.     

Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design

Answering an open question published in Operations Research (54, 73–91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time. X. Chen is Visiting Fellow, University of Warwick.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

Approximation algorithms for the Fault-Tolerant Facility Placement problem

In the Fault-Tolerant Facility Placement problem (FTFP) we are given a set of customers C, a set of sites F, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j has a demand rj and each site may open an unbounded number of facilities. The objective is to minimize the total cost of opening facilities and connecting each customer j to rj different open facilities. We present two LP-rounding algorithms for FTFP. The first algorithm achieves an approximation ratio of 4. The second algorithm uses the method of filtering to improve the ratio to 3.16.     

An Approximation Algorithm for a Large-Scale Facility Location Problem

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy—Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in ( O (3n + 2n log n ) ) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9%-11%, that the Interchange heuristic improved the total cost by an additional 0.5%—1.5%, and that Balloon Search improved it by a further 0.5%—1.5%.     

Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks

Abstract. A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of n independent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed ε > 0 , computes in O(n) time a non-preemptive schedule of length at most (1+ε) times the optimum.     

一般设施定位问题计算复杂度和近似算法研究

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243 0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1 ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.     

A Local Facility Location Algorithm for Large-scale Distributed Systems

In a facility location problem (FLP) we are given a set of facilities and a set of clients, each of which is to be served by one facility. The goal is to decide which subset of facilities to open, such that the clients will be served at a minimal cost. In this paper we investigate the FLP in a setting where the cost depends on data known only to the clients. This setting typifies modern distributed systems: peer-to-peer file sharing networks, Grid systems, and wireless sensor networks. All of them need to perform network organization, data placement, collective power management, and other tasks of this kind. We propose a local and efficient algorithm that solves FLP in these settings. The algorithm presented here is extremely scalable, entirely decentralized, requires no routing capabilities, and is resilient to failures and changes in the data throughout its execution.     

An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [?-approximation with minimum packing constraint violation, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (≈2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.     

An Approximation Algorithm for Circular Arc Colouring

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1+1/e (approximately 1.37) except when the minimum number of colours required is very small (O(ln n) ). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource. Received October 25, 1998; revised August 26, 1999, and April 17, 2000.     

A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et?al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.     

The Power of Priority Algorithms for Facility Location and Set Cover

We apply and extend the priority algorithm framework introduced by Borodin, Nielsen, and Rackoff to define greedy-like algorithms for the (uncapacitated) facility location problems and set cover problems. These problems have been the focus of extensive research from the point of view of approximation algorithms and for both problems greedy-like algorithms have been proposed and analyzed. The priority algorithm definitions are general enough to capture a broad class of algorithms that can be characterized as greedy-like while still possible to derive non-trivial lower bounds on the approximability of the problems by algorithms in such a class. Our results are orthogonal to complexity considerations, and hence apply to algorithms that are not necessarily polynomial time.     

On the Competitive Ratio for Online Facility Location

We consider the problem of Online Facility Location, where the demand points arrive online and must be assigned irrevocably to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We prove that the competitive ratio for Online Facility Location is Θ . On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than Ω against an oblivious adversary even if the demands lie on a line segment. On the positive side, we present a deterministic algorithm which achieves a competitive ratio of in every metric space. A preliminary version of this work appeared in the Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science 2719. This work was done while the author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany, and was partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM–FT).     

The reverse greedy algorithm for the metric k-median problem

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn).     

多处理器任务调度问题的新近似算法

研究任务有多种处理方式的多处理器任务调度问题（MTS）的求解算法，给出求解这种问题的二阶段方法：第1阶段为指派问题，第二阶段调度问题Pm｜fixj｜Cmax，从而得到一个新的求解Pm｜setj｜Cmax。近似算法的方法，并针对P4｜fixj｜Cmax给出了具体算法，证明这种近似算法是一个2-逼近度算法，是文献中在4-处理器问题上的推广。     

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.     

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R ⁺, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k _u . A solution consists of a function x:V→ℕ₀ and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x _u k _u . Our objective is to find a cover that minimizes ∑ _v∈V x _v w _v . This is the first 2-approximation for the problem and also runs in O(nlog n+m) time. Research supported by NSF Awards CCR 0113192 and CCF 0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

最小生成树的高效异步并行算法

在ＭＩＭＤ－ＳＭ并行计算模型上，本文给出了时间复杂性为Ｏ（ｎ（ｎ／ｐ＋ｌｏｇｐ））的最小生成树的异步并行算法，其中ｎ，ｐ（１≤ｐ≤ｎ）分别表示图的顶点数和处理机的个数。