Local search algorithm for universal facility location problem with linear penalties

详细信息    查看全文

• 作者：Yicheng Xu ; Dachuan Xu ; Donglei Du ; Chenchen Wu
• 关键词：Approximation algorithm ; Universal facility location problem ; Linear penalty ; Local search
• 刊名：Journal of Global Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：67
• 期：1-2
• 页码：367-378
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Optimization; Operation Research/Decision Theory; Real Functions; Computer Science, general;
• 出版者：Springer US
• ISSN：1573-2916
• 卷排序：67

文摘

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.