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
Authors
Funding
Bibliographic Details
- 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
Item Description
- 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
- Copyright holder:
- ACM
- Copyright date:
- 2016
- Notes:
- Copyright © 2016 ACM. This is the accepted manuscript version of the article. The final version is available online from Association for Computing Machinery at: http://dx.doi.org/10.1145/2850419
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record