Oracle Tractability of Skew Bisubmodular Functions

Huber, A.; Krokhin, A.

Abstract

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use this extension to show that skew bisubmodular functions given by an oracle can be minimized in polynomial time.

Citation

Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038

• Journal Article Type: Article
• Acceptance Date: Aug 11, 2014
• Online Publication Date: Oct 14, 2014
• Publication Date: Oct 14, 2014
• Deposit Date: Oct 16, 2014
• Publicly Available Date: Oct 17, 2014
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 28
• Issue: 4
• Pages: 1828-1837
• DOI: https://doi.org/10.1137/130936038
• Keywords: Submodular functions, Optimization, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1452220