A COST-SHARING METHOD FOR AN UNCAPACITATED FACILITY LOCATION GAME WITH PENALTIES

被引：1

作者：

Zhen WANG ^{[1
]}

Dachuan XU ^{[1
]}

机构：

[1] Department of Applied Mathematics,Beijing University of Technology

来源：

Journal of Systems Science & Complexity | 2012年 / 25卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Cost-sharing method; cross-monotonicity; facility location game;

D O I：

暂无

中图分类号：

O242.1 [数学模拟];

学科分类号：

070102 ;

摘要：

This paper considers a variant of the classical facility location game called the uncapacitated facility location game with penalties(UFLGWP).Unlike the standard UFLG,each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty.The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.

引用

页码：287 / 292

页数：6

共 6 条

[1]

Soft-capacitated Facility Location Game[J]. Yu Li~1,Da-chuan Xu~(2*) 1 Department of Mathematics,School of Science,Beijing Jiaotong University,Beijing 100044,China 2 Department of Applied Mathematics,College of Applied Sciences,Beijing University of Technology,Beijing 100124,China. Acta Mathematicae Applicatae Sinica(English Series). 2010(01)

[2] An improved approximation algorithm for uncapacitated facility location problem with penalties [J].

Xu, Guang ;

Xu, Jinhui .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) :424-436

[3] Approximating the two-level facility location problem via a quasi-greedy approach [J].

Zhang, Jiawei .

MATHEMATICAL PROGRAMMING, 2006, 108 (01) :159-176

[4] An LP rounding algorithm for approximating uncapacitated facility location problem with penalties [J].

Xu, G ;

Xu, JH .

INFORMATION PROCESSING LETTERS, 2005, 94 (03) :119-123

[5]

Strategyproof sharing of submodular costs:budget balance versus efficiency[J] . Hervé Moulin,Scott Shenker. Economic Theory . 2001 (3)

[6]

A 3-approximation algorithm for the k -level uncapacitated facility location problem[J] . Karen Aardal,Fabián A. Chudak,David B. Shmoys. Information Processing Letters . 1999 (5)

← 1 →