Maximizing k -Submodular Functions and Beyond
Authors:
Open Access
- 3 August 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 12 (4) , 1-26
Abstract
We consider the maximization problem in the value oracle model of functions defined on k -tuples of sets that are submodular in every orthant and r -wise monotone, where k ⩾ 2 and 1 ⩽ r ⩽ k . We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1 + r ). For r = k , we give an analysis of a randomized greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+√ k /2. In the case of k = r = 2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible both in the value query model and under the assumption that NP ≠ RP . Extending a result of Ando et al., we show that for any k ⩾ 3, submodularity in every orthant and pairwise monotonicity (i.e., r = 2) precisely characterize k -submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k ) for the maximization problem of k -submodular functions.Keywords
All Related Versions
Funding Information
- Royal Society University Research Fellowship
- EPSRC (EP/J021814/1 and EP/D063191/1)
This publication has 32 references indexed in Scilit:
- Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimizationMathematical Programming, 2008
- A faster strongly polynomial time algorithm for submodular function minimizationMathematical Programming, 2007
- The complexity of soft constraint satisfactionArtificial Intelligence, 2006
- K-submodular functions and convexity of their Lovász extensionDiscrete Applied Mathematics, 2002
- A Fully Combinatorial Algorithm for Submodular Function MinimizationJournal of Combinatorial Theory, Series B, 2002
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001
- A characterization of bisubmodular functionsDiscrete Mathematics, 1996
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- PseudomatroidsDiscrete Mathematics, 1988
- Submodular functions and convexity1983