On $k$-Submodular Relaxation

DOI10.1137/15M101926XzbMath1344.05034arXiv1504.07830OpenAlexW3105827122MaRDI QIDQ2820856

Hiroshi Hirai, Yuni Iwamasa

Publication date: 9 September 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.07830

zbMATH Keywords

valued constraint satisfaction problems\(k\)-submodular function\(k\)-submodular relaxation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Other designs, configurations (05B30)

Related Items (7)

A compact representation for minimizers of \(k\)-submodular functions ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ Discrete Midpoint Convexity ⋮ Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)

Cites Work

• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Submodular functions and optimization.
• Half-integrality, LP-branching, and FPT Algorithms
• Towards Minimizing k-Submodular Functions
• Improved Approximation Algorithms for k-Submodular Function Maximization
• The Complexity of Valued Constraint Satisfaction Problems
• Maximizing k -Submodular Functions and Beyond
• A Min-Max Theorem for Transversal Submodular Functions and Its Implications
• The Power of Linear Programming for General-Valued CSPs
• Ideals and the binary discriminator in universal algebra

This page was built for publication: On $k$-Submodular Relaxation