Huber, A. and Krokhin, A. (2014) 'Oracle tractability of skew bisubmodular functions.', SIAM journal on discrete mathematics., 28 (4). pp. 1828-1837.
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.
| Item Type: | Article |
|---|---|
| Keywords: | Submodular functions, Optimization, Computational complexity. |
| Full text: | (AM) Accepted Manuscript Download PDF (298Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1137/130936038 |
| Publisher statement: | © 2014, Society for Industrial and Applied Mathematics |
| Date accepted: | 11 August 2014 |
| Date deposited: | 17 October 2014 |
| Date of first online publication: | 14 October 2014 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
