Submodular Function Minimization under Covering Constraints
Authors:
- Satoru IwataSISatoru Iwata
- Kiyohito NaganoKNKiyohito Nagano
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 671-680
Abstract
This paper addresses the problems of minimizing nonnegative submodular functions under covering constraints, which generalize the vertex cover, edge cover, and set cover problems. We give approximation algorithms for these problems exploiting the discrete convexity of submodular functions. We first present a rounding 2-approximation algorithm for the submodular vertex cover problem based on the half-integrality of the continuous relaxation problem, and show that the rounding algorithm can be performed by one application of submodular function minimization on a ring family. We also show that a rounding algorithm and a primal-dual algorithm for the submodular cost set cover problem are both constant factor approximation algorithms if the maximum frequency is fixed. In addition, we give an essentially tight lower bound on the approximability of the submodular edge cover problem.Keywords
This publication has 25 references indexed in Scilit:
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds2008
- Optimal approximation for the submodular welfare problem in the value oracle model2008
- A faster strongly polynomial time algorithm for submodular function minimizationMathematical Programming, 2007
- A Faster Scaling Algorithm for Minimizing Submodular FunctionsSIAM Journal on Computing, 2003
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Minimizing submodular functions over families of setsCombinatorica, 1995
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequalityMathematical Programming, 1993
- Geometric Algorithms and Combinatorial Optimization1988
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981