A note on submodular set cover on matroids

被引：5

作者：

Gargano, Luisa ^{[1
]}

Hammar, Mikael ^{[2
]}

机构：

[1] Univ Salerno, Dipartimento Informat & Applicaz, I-84084 Fisciano, SA, Italy

[2] Apptus Technol AB, Res & Dev, S-22370 Lund, Sweden

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 18期

关键词：

Matroid; Independent sets; Set cover; ALGORITHM;

D O I：

10.1016/j.disc.2008.05.019

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：5739 / 5744

页数：6

共 17 条

[1]

[Anonymous], 1999, COMPLEXITY APPROXIMA, DOI DOI 10.1007/978-3-642-58412-1

[2]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[3]

[Anonymous], 1929, MONATSCHRIFT MATH PH

[4]

Birkhoff G, 1933, P CAMB PHILOS SOC, V29, P441

[5]

Edmonds Jack, 1970, Lecture Notes in Comput. Sci., P69

[6]

ELKIN M, 2003, P ICALP

[7] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[8]

FISHER ML, 1978, MATH PROGRAM STUD, V8, P73, DOI 10.1007/BFb0121195

[9] A WEIGHTED MATROID INTERSECTION ALGORITHM [J].

FRANK, A .

JOURNAL OF ALGORITHMS, 1981, 2 (04) :328-336

[10] ON THE SUBDIFFERENTIAL OF A SUBMODULAR FUNCTION [J].

FUJISHIGE, S .

MATHEMATICAL PROGRAMMING, 1984, 29 (03) :348-360

← 1 2 →