The Library
Maximizing bisubmodular and k-submodular functions
Tools
Ward, Justin and Živný, Stanislav (2014) Maximizing bisubmodular and k-submodular functions. In: SODA '14, Portland, Ohio, 5-7 Jan 2014. Published in: SODA '14 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1468-1481. ISBN 9781611973389. doi:10.1137/1.9781611973402.108
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/1.9781611973402.108
Abstract
Submodular functions play a key role in combinatorial optimization and in the study of valued constraint satisfaction problems. Recently, there has been interest in the class of bisubmodular functions, which assign values to disjoint pairs of sets. Like submodular functions, bisubmodular functions can be minimized exactly in polynomial time and exhibit the property of diminishing returns common to many problems in operations research. Recently, the class of k-submodular functions has been proposed. These functions generalize the notion of submodularity to k-tuples of sets, with submodular and bisubmodular functions corresponding to k = 1 and 2, respectively.
In this paper, we consider the problem of maximizing bisubmodular and, more generally, k-submodular functions in the value oracle model. We provide the first approximation guarantees for maximizing a general bisubmodular or k-submodular function. We give an analysis of the naive random algorithm as well as a randomized greedy algorithm inspired by the recent randomized greedy algorithm of Buchbinder et al. [FOCS'12] for unconstrained submodular maximization. We show that this algorithm approximates any k-submodular function to a factor of .
In the case of bisubmodular functions, our randomized greedy algorithm gives an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that NP ≠ RP. Our analysis provides further intuition for the algorithm of Buchbinder et al. [FOCS'12] in the submodular case. Additionally, we show that the naive random algorithm gives a 1/4-approximation for bisubmodular functions, corresponding again to known performance guarantees for submodular functions. Thus, bisubmodular functions exhibit approximability identical to submodular functions in all of the algorithmic contexts we consider.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | SODA '14 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
Publisher: | ACM ; SIAM | ||||
ISBN: | 9781611973389 | ||||
Book Title: | Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
Editor: | Chekuri, Chandra | ||||
Official Date: | 2014 | ||||
Dates: |
|
||||
Page Range: | pp. 1468-1481 | ||||
DOI: | 10.1137/1.9781611973402.108 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||
Grant number: | EP/J021814/1; EP/D063191/1 | ||||
Embodied As: | 1 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | SODA '14 | ||||
Type of Event: | Conference | ||||
Location of Event: | Portland, Ohio | ||||
Date(s) of Event: | 5-7 Jan 2014 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |