Oracle tractability of skew bisubmodular functions

Anna Huber, Andrei Krokhin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1828-1837
Number of pages10
JournalSIAM Journal on Discrete Mathematics
Issue number4
Publication statusPublished - 14 Oct 2014


Dive into the research topics of 'Oracle tractability of skew bisubmodular functions'. Together they form a unique fingerprint.

Cite this