Minimization Problems with Non-Submodular Cover Constraint

被引：0

作者：

Wang, Wenqi ^{[1
,2
]}

Liu, Zhicheng ^{[3
]}

Du, Donglei ^{[4
]}

Shi, Peihao ^{[5
]}

Zhang, Xiaoyan ^{[1
,2
]}

机构：

[1] Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Peoples R China

[2] Nanjing Normal Univ, Inst Math, Nanjing 210023, Peoples R China

[3] Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

[4] Univ New Brunswick, Fac Management, Fredericton, NB E3B 9Y2, Canada

[5] Ind Technol Res Inst Co Ltd, Nanjing Kinghua Operat Res & ArtificialIntelligenc, Nanjing 210035, Peoples R China

来源：

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2023年 / 40卷 / 05期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Approximation algorithm; submodular function; combinatorial optimization; greedy algorithm; primal-dual algorithm; ALGORITHM;

D O I：

10.1142/S0217595923400122

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovasz extension, we devise greedy and primal-dual approximation algorithms for these problems.

引用

页数：19

共 24 条

[1]

Calinescu Gruia., 2007, Maximizing a submodular set function subject to a matroid constraint

[2]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[3] Analytical Approach to Parallel Repetition [J].

Dinur, Irit ;

Steurer, David .

STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :624-633

[4]

Edmonds J., 1970, Combinatorial struc- tures and their applications, P69

[5]

Fleischer L, 2003, DISCRETE APPL MATH, V25, P169

[6] Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions [J].

Goel, Gagan ;

Karande, Chinmay ;

Tripathi, Pushkar ;

Wang, Lei .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :755-764

[7] THE ELLIPSOID METHOD AND ITS CONSEQUENCES IN COMBINATORIAL OPTIMIZATION [J].

GROTSCHEL, M ;

LOVASZ, L ;

SCHRIJVER, A .

COMBINATORICA, 1981, 1 (02) :169-197

[8]

Grotschel M., 1988, GEOMETRIC ALGORITHMS

[9] A combinatorial strongly polynomial algorithm for minimizing submodular functions [J].

Iwata, S ;

Fleischer, L ;

Fujishige, S .

JOURNAL OF THE ACM, 2001, 48 (04) :761-777

[10] Submodular Function Minimization under Covering Constraints [J].

Iwata, Satoru ;

Nagano, Kiyohito .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :671-680

← 1 2 3 →