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.     

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.     

软容量限制设施选址问题的竞争决策算法

软容量设施选址问题是NP-Hard问题之一，具有广泛的应用价值。为了求解软容量设施选址问题，提出一种基于数学性质的竞争决策算法。首先研究该问题的数学性质，运用这些数学性质不仅可以确定某些设施必定开设或关闭，还可以确定部分顾客由哪个设施提供服务，从而缩小问题的规模，加快求解速度。在此基础上设计了求解该问题的竞争决策算法，最后经过一个小规模的算例测试并与精确算法的结果比较，得出了最优解；针对大规模的问题快速地求出了可行解，得到了令人满意的结果。     

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.     

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%.     

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%.     

基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

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 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.     

带惩罚的无容量设施选址问题的降阶回溯算法

无容量设施选址问题（Uncapacitated Facility Location Problem,UFLP）是组合优化中经典的NP-Hard问题之一。针对UFLP的变形问题之一,即带惩罚的无容量设施选址问题（Uncapacitated Facility Location Problem With Penalties,UFLPWP）,研究了UFLPWP的数学性质,其中包括可以批量确定某些设施一定关闭的性质,并进行了数学证明,利用这些数学性质可以对问题进行降阶,进而缩小问题的规模。在此基础上设计了基于上、下界的回溯算法来求解UFLPWP。通过一个示例分析,进一步阐述该算法的原理。     

具有逻辑路由跳数O(1)的可扩展的分散式查找算法

对等网络中的一个基本问题就是如何高效地进行数据查找．分散式查找是解决这类问题的一种新思路．现有的分散式查找方法在查找时所需的逻辑路由跳数都与网络中的节点数相关(一般为O(logn),少数为O(n^1/c)．Sifter是一种可扩展、自组织、高容错和高效率的分散式查找算法．在该算法中,单个节点只需维护O(n1／c)个其他节点的链接信息,就能够在O(1)个逻辑路由跳内找到目的数据．该算法适用于网络动态性不大,但是对查找的实时性要求较高的应用．     

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

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

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.     

A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties

The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706).     

Robust Facility Location Problem for Hazardous Waste Transportation

We consider a robust facility location problem for hazardous materials (hazmat) transportation considering routing decisions of hazmat carriers. Given a network and a known set of nodes from which hazmat originate, we compute the locations of hazmat processing sites (e.g. incinerators) which will minimize total cost, in terms of fixed facility cost, transportation cost, and exposure risk. We assume that hazmat will be taken to the closest existing processing site. We present an exact full enumeration method, which is useful for small or medium-size problems. For larger problems, the use of a genetic algorithm is explored. Through numerical experiments, we discuss the impact of uncertainty and robust optimization in the hazmat combined location-routing problem.     

一种加权距离连续K中心选址问题求解方法

K中心选址作为一种经典问题,学者们提出了很多好的解决方法,但是对于加权距离连续K中心选址问题的研究一直没有很好的进展.本文针对连续K中心选址问题,以最小加权距离作为优化目标提出改进的粒子群优化算法(SA-PSO).本文将模拟退火机制引入PSO算法并且加入惯性权重等策略对算法进行改进,使得该算法可以更快收敛于全局最优.仿真实验结果表明,SA-PSO算法相比于GA算法和K-means算法,具有更强的稳定性,收敛速度更快,并且优化得到的加权距离更小.     

一种面向仿真的分布式多智能体层次问题求解算法

多智能体分布问题求解复杂度与其组织结构紧密相关,在层次组织中进行多层问题抽象以及子问题并行求解,可以将复杂度为指数规模问题规约为对数规模问题.本文使用基于角色层次组织模型,集成人工智能中已有快速求解算法,提出一种面向仿真的层次式多智能体问题求解算法.算法具有良好的计算复杂度、灵活性与可扩展性,已应用于战场仿真中多智能体的协同.