Skip to main content

Research Repository

Advanced Search

Oracle Tractability of Skew Bisubmodular Functions

Huber, A.; Krokhin, A.

Oracle Tractability of Skew Bisubmodular Functions Thumbnail


Authors

A. Huber



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 Mar 28, 2024
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.

Files

Accepted Journal Article (305 Kb)
PDF

Copyright Statement
© 2014, Society for Industrial and Applied Mathematics





You might also like



Downloadable Citations