Journal article icon

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 ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
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
Name:
Royal Society
Funding agency for:
Zivny, S
Publisher:
Association for Computing Machinery
Journal:
ACM Transactions on Algorithms More from this journal
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

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP