Oracle Tractability of Skew Bisubmodular Functions
Anna Lena Huber, Andrei Krokhin · SIAM Journal on Discrete Mathematics · 2014
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.