Towards Minimizing k-Submodular Functions

DOI10.1007/978-3-642-32147-4_40zbMath1370.90219arXiv1309.5469OpenAlexW1930126570MaRDI QIDQ3167647

Vladimir Kolmogorov, Anna Huber

Publication date: 2 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27)

Related Items (29)

On a general framework for network representability in discrete optimization ⋮ A compact representation for minimizers of \(k\)-submodular functions ⋮ Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ On maximizing a monotone \(k\)-submodular function under a knapsack constraint ⋮ Information coverage maximization for multiple products in social networks ⋮ Maximization of \(k\)-submodular function with a matroid constraint ⋮ Weakly \(k\)-submodular maximization under matroid constraint ⋮ Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ Profit maximization for multiple products in community-based social networks ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ The Complexity of Valued CSPs ⋮ L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ A compact representation for modular semilattices and its applications ⋮ Unnamed Item ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ On $k$-Submodular Relaxation ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Improved Randomized Algorithm for k-Submodular Function Maximization ⋮ k-Submodular maximization with two kinds of constraints

This page was built for publication: Towards Minimizing k-Submodular Functions