期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

A cross-monotonic cost sharing method for the facility location game with service installation costs 被引量：4

A cross-monotonic cost sharing method for the facility location game with service installation costs
原文传递
导出
摘要 In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type. In this paper, we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.
作者 XU DaChuan Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China
出处 《Science China Mathematics》 SCIE 2009年第11期2530-2536,共7页 中国科学：数学（英文版）
基金 supported by National Natural Science Foundation of China (Grant Nos. 60773185, 10401038) Program for Beijing Excellent Talents (Grant No. 20071D050150020S)
关键词 facility location game cross-monotonic cost-sharing method linear programming relaxation 90C27 91A12 facility location game cross-monotonic cost-sharing method linear programming relaxation
分类号 F275 [经济管理—企业管理]
  • 相关文献

参考文献27

  • 1Jiawei Zhang.Approximating the two-level facility location problem via a quasi-greedy approach[J]. Mathematical Programming . 2006 (1)
  • 2Hervé Moulin,Scott Shenker.Strategyproof sharing of submodular costs:budget balance versus efficiency[J]. Economic Theory . 2001 (3)
  • 3Byrka J,Aardal K.An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing . 2009
  • 4Li Y,Xu D.Soft-capacitated facility location game. Acta Math Appl Sin Engl Ser .
  • 5Devanur N R,Mihail M,Vazirani V V.Strategyproof cost-sharing mechanisms for set cover and facility location games. Decis Supp Syst . 2005
  • 6Shmoys D,Tardos E,Aardal K.Approximation algorithms for facility location problems (extended ab- stract). Proceedings of the 29th ACM Symposium on Theory of Computing (STOC) . 1997
  • 7Guha S,Khuller S.Greedy strike back: Improved facility location algorithms. Journal of Algorithms . 1999
  • 8Jain K,Mahdian M,Saberi A.A new greedy approach for facility location problems. Proceedings of the 34th ACM Symposium on Theory of Computing (STOC) . 2002
  • 9Du D,Wang X,Xu D.An approximation algorithm for the k-level capacitated facility location problem. J Comb Optim .
  • 10Shmoys D,Swamy C,Levi R.Facility location with service installation costs. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . 2004

同被引文献12

  • 1Yu Li,Donglei Du,Naihua Xiu,Dachuan Xu.A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties[J].Journal of Combinatorial Optimization.2014(3)
  • 2Ankit Aggarwal,Anand Louis,Manisha Bansal,Naveen Garg,Neelima Gupta,Shubham Gupta,Surabhi Jain.A 3-approximation algorithm for the facility location problem with uniform capacities[J].Mathematical Programming (-).2013(1-2)
  • 3Weng Kerui.Approximation algorithm for uniform bounded facility location problem[J].Journal of Combinatorial Optimization.2013(2)
  • 4Gaidi Li,Zhen Wang,Chenchen Wu.Approximation algorithms for the stochastic priority facility location problem[J].Optimization.2013(7)
  • 5Yu Li,Jia Shu,Xi Wang,Naihua Xiu,Dachuan Xu,Jiawei Zhang.Approximation Algorithms for Integrated Distribution Network Design Problems[J].INFORMS Journal on Computing.2013(3)
  • 6Shi Li.A 1.488 approximation algorithm for the uncapacitated facility location problem[J].Information and Computation.2013
  • 7Yu Li,Dachuan Xu,Donglei Du,Naihua Xiu.Improved approximation algorithms for the robust fault-tolerant facility location problem[J].Information Processing Letters.2012(10)
  • 8Yu Li,Donglei Du,Naihua Xiu,Dachuan Xu.A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties[J].Theoretical Computer Science.2012
  • 9Donglei Du,Ruixing Lu,Dachuan Xu.A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties[J].Algorithmica (-).2012(1-2)
  • 10Zachary Friggstad,Mohammad R. Salavatipour.Minimizing movement in mobile facility location problems[J].ACM Transactions on Algorithms (TALG).2011(3)

引证文献4

二级引证文献8

Science China Mathematics
2009年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部