Submodularity of some classes of the combinatorial optimization games

被引：21

作者：

Okamoto, Y ^{[1
]}

机构：

[1] ETH, Dept Comp Sci, Inst Theoret Comp Sci, CH-8092 Zurich, Switzerland

来源：

MATHEMATICAL METHODS OF OPERATIONS RESEARCH | 2003年 / 58卷 / 01期

关键词：

combinatorial optimization; game theory; submodularity;

D O I：

10.1007/s001860300284

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Submodularity (or concavity) is considered as an important property in the field of cooperative game theory. In this article, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game on a given graph is submodular or not. Related to these results, the Shapley values are also investigated.

引用

页码：131 / 139

页数：9

共 18 条

[1]

BILBAO J. M., 2000, Cooperative games on combinatorial structures

[2]

Cook W., 1998, Combinatorial Optimization

[3]

Curiel I., 1997, COOPERATIVE GAME THE

[4] Algorithmic aspects of the core of combinatorial optimization games [J].

Deng, XT ;

Ibaraki, T ;

Nagamochi, H .

MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (03) :751-766

[5] Totally balanced combinatorial optimization games [J].

Deng, XT ;

Ibaraki, T ;

Nagamochi, H ;

Zang, WN .

MATHEMATICAL PROGRAMMING, 2000, 87 (03) :441-452

[6]

Diestel R., 1997, Graph Theory

[7]

Edmonds J., 1971, Math. Program, V1, P127, DOI [DOI 10.1007/BF01584082, 10.1007/BF01584082]

[8]

Fujishige S., 1991, SUBMODULAR FUNCTIONS

[9]

KARP RM, 1972, COMPLEXITY COMPUTER, P885

[10]

Korte B., 2011, Combinatorial Optimization, V5th

← 1 2 →