Back to Search
Start Over
SUBMODULAR APPROXIMATION: SAMPLING-BASED ALGORITHMS AND LOWER BOUNDS.
- Source :
-
SIAM Journal on Computing . 2011, Vol. 40 Issue 6, p1715-1737. 23p. - Publication Year :
- 2011
-
Abstract
- We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-make span scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees that most of our algorithms achieve are of the order of √n/ln n. We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem f approximating a monotone submodular function everywhere. In addition, we present an algorithm for approximating submodular functions with a special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMPUTER science
*MATROIDS
*SUBMODULAR functions
*ALGORITHMS
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 40
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 71607606
- Full Text :
- https://doi.org/10.1137/100783352