Oracle tractability of skew bisubmodular functions

Anna Huber, Andrei Krokhin

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.

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

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

  • Profiles

    Cite this