Towards minimizing k-submodular functions Conference Paper

Author(s): Huber, Anna; Kolmogorov, Vladimir
Title: Towards minimizing k-submodular functions
Title Series: LNCS
Affiliation IST Austria
Abstract: In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively. In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.
Conference Title: ISCO: International Symposium on Combinatorial Optimization
Volume: 7422
Conference Dates: April 17-21, 2012
Conference Location: Athens, Greece
ISBN: 978-3-642-32146-7
Publisher: Springer  
Date Published: 2012-01-01
Start Page: 451
End Page: 462
DOI: 10.1007/978-3-642-32147-4_40
Notes: We would like to thank Andrei Krokhin for encourag- ing our cooperation, for helpful discussions, and for his critical reading of the manuscript.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work