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.     

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

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.     

具有逻辑路由跳数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.     

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

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

分布式文件系统中文件位置无关性的一个解决方案

在分布式文件系统中文件的"位置无关性”是一个重要的要求,有了它可以使文件在服务器之间自由移动而不影响到客户端程序的运行,同时达到平衡服务器负载的目的,以提高系统整体性能.本文讨论了一种简单易行的方法来实现文件的"位置无关性”.     

家族保护遗传算法(KPGA)解决设备布局问题的研究

分析了影响遗传算法全局搜索能力的因素,并有针对性地提出一种新的变形遗传算法——家族保护遗传算法(Kindred-Protectcd GA,KPGA),以提高算法的全局搜索能力和计算性能.同时以经典设备布局问题为例进行探讨,将结果与Chae、Junjae等采用一般遗传算法得出的结果、以及与Jajodia等人采用模拟退火算法得出的结果相比较,发现KPGA得出的布局结果有明显的改善.     

测量协同问题研究--完全分布式的解决方案

精确性是网络测量的一个关键问题．一个测量节点对测量任务的并发执行通常会影响测量结果的精确性。测量任务的互斥执行可以降低或消除这种影响．同时．单向测量需要两个节点协作进行。因此随机产生的测量任务可能会产生冲突．从而导致进程死锁、测量效率低下等一系列问题．我们称该类问题为测量协同问题(MCP)．MCP是一类特殊的分布式资源分配问题．它的特殊性主要在于：(1)资源之间协商该被哪个进程(任务)使用;(2)如果任务的资源需求得不到满足．则该任务将被放弃执行．作者提出了测量协同问题完全分布式的算法——CDA．证明了CDA的存活性和正确性．并分析了消息复杂度、空间复杂度和收敛时间．模拟实验表明．CDA具有良好的处理冲突任务的能力．使得CDA在任务并发性较强时仍然具有较好的任务执行能力．     

基于遗传模拟退火算法的多层设施选址方法

逆向物流网络是逆向物流系统高效运作的基础和前提,而设施的选址定位是逆向物流网络设计的核心问题.为此,提出一个多层设施选址模型,旨在构建由回收点、回收中心和生产点相结合的最佳逆向物流回收网络.根据模型特点,提出基于遗传模拟退火算法的求解方法,个体采用二进制十进制混合编码;提出基于Metropolis准则的特定遗传进化操作;设计顾客对回收点、回收点对回收中心的两个子分配算法保证所有约束的满足性.最后通过仿真实验,得到满意的设施选址方案.可见,选址模型和算法是一种有效的设施选址方法,具有一定的应用前景.