Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions

V. Kolmogorov, in:, Springer, 2011, pp. 400–411.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms.
Publishing Year
Date Published
2011-08-09
Volume
6907
Page
400 - 411
Conference
MFCS: Mathematical Foundations of Computer Science
IST-REx-ID

Cite this

Kolmogorov V. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. In: Vol 6907. Springer; 2011:400-411. doi:10.1007/978-3-642-22993-0_37
Kolmogorov, V. (2011). Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions (Vol. 6907, pp. 400–411). Presented at the MFCS: Mathematical Foundations of Computer Science, Springer. https://doi.org/10.1007/978-3-642-22993-0_37
Kolmogorov, Vladimir. “Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions,” 6907:400–411. Springer, 2011. https://doi.org/10.1007/978-3-642-22993-0_37.
V. Kolmogorov, “Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions,” presented at the MFCS: Mathematical Foundations of Computer Science, 2011, vol. 6907, pp. 400–411.
Kolmogorov V. 2011. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907. 400–411.
Kolmogorov, Vladimir. Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions. Vol. 6907, Springer, 2011, pp. 400–11, doi:10.1007/978-3-642-22993-0_37.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar