# Journal article

## Maximizing k-submodular functions and beyond

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\geq 2$ and $1\leq r\leq 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 randomised greedy algorithm that shows that any such function can be approximated to a factor of $1/(1+\sqrt{k/2})$. In ...

Publication status:
Published
Peer review status:
Peer reviewed

### Access Document

Files:
• (Accepted manuscript, pdf, 363.8KB)
Publisher copy:
10.1145/2850419

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Zivny, S
Publisher:
Association for Computing Machinery Publisher's website
Journal:
ACM Transactions on Algorithms Journal website
Volume:
12
Issue:
4
Article number:
47
Publication date:
2016-01-01
DOI:
EISSN:
1549-6333
ISSN:
1549-6325
Keywords:
Pubs id:
pubs:484001
UUID:
uuid:8de1b5f4-70a0-4aaa-a557-3185f9bc1c26
Local pid:
pubs:484001
Source identifiers:
484001
Deposit date:
2015-11-20