Towards Minimizing k-Submodular Functions

2013/09/21 by Anna Huber, Vladimir Kolmogorov, Huber, Anna +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1309.5469

openalex publication_date 2013/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 and investigate a k-submodular polyhedron and prove a Min-Max-Theorem for k-submodular functions.

Citations

• Min CSP on Four Elements: Moving Beyond Submodularity

Cited by

• A 1/2-Approximation for Budgeted k-Submodular Maximization
• Deep Submodular Functions

Related

• Improved Approximation Algorithms for k-Submodular Function Maximization
• Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
• A compact representation for minimizers of k-submodular functions
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• On maximizing a monotone k-submodular function under a knapsack constraint