A note on the submodular vertex cover problem with submodular penalties

被引：5

作者：

Kamiyama, Naoyuki ^{[1
,2
]}

机构：

[1] Kyushu Univ, Inst Math Ind, Fukuoka 812, Japan

[2] JST, PRESTO, Kawaguchi, Saitama, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2017年 / 659卷

关键词：

Submodular functions; The vertex cover problem; The set cover problem;

D O I：

10.1016/j.tcs.2016.10.017

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we prove that there exists a combinatorial 3-approximation algorithm for the submodular vertex cover problem with submodular penalties introduced by Xu, Wang, Du, and Wu. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：95 / 97

页数：3

共 3 条

[1] 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

[2] Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties [J].

Li, Yu ;

Du, Donglei ;

Xiu, Naihua ;

Xu, Dachuan .

ALGORITHMICA, 2015, 73 (02) :460-482

[3] Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique [J].

Xu, Dachuan ;

Wang, Fengmin ;

Du, Donglei ;

Wu, Chenchen .

THEORETICAL COMPUTER SCIENCE, 2016, 630 :117-125

← 1 →