On $k$-Submodular Relaxation
From MaRDI portal
Publication:2820856
DOI10.1137/15M101926XzbMath1344.05034arXiv1504.07830OpenAlexW3105827122MaRDI QIDQ2820856
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
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
