Submodular Function Minimization under Covering Constraints

DOI10.1109/FOCS.2009.31MaRDI QIDQ5171203zbMATH OpenFDO

Authors Satoru Iwata, Kiyohito Nagano

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2009.31

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cited in

(41)

• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Supermodular covering knapsack polytope
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Complexity and approximations for submodular minimization problems on two variables per inequality constraints
• Equivalence of convex minimization problems over base polytopes
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• Robust budget allocation via continuous submodular functions
• Approximation algorithms for the submodular edge cover problem with submodular penalties
• Approximation algorithm for stochastic set cover problem
• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
• New approximations and hardness results for submodular partitioning problems
• Minimum hitting set of interval bundles problem: computational complexity and approximability
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
• The multi-budget maximum weighted coverage problem
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• Half-integrality, LP-branching, and FPT algorithms
• Submodular function minimization under a submodular set covering constraint
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Submodular Cost Allocation Problem and Applications
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
• Generalized roof duality and bisubmodular functions
• Submodular functions: learnability, structure, and optimization
• Evader interdiction: algorithms, complexity and collateral damage
• LP-based covering games with low price of anarchy
• Algorithm 996
• Multi-agent submodular optimization
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Algorithms for maximizing monotone submodular function minus modular function under noise
• Approximability of sparse integer programs
• Minimization problems with non-submodular cover constraint
• Generalized class cover problem with axis-parallel strips
• Online dynamic submodular optimization
• Approximation algorithms for the submodular hitting set problem
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Approximate cores of submodular cost set cover games
• Shortest cycles with monotone submodular costs
• A note on submodular function minimization with covering type linear constraints
• A note on the submodular vertex cover problem with submodular penalties
• An approximation algorithm for submodular hitting set problem with linear penalties

This page was built for publication: Submodular Function Minimization under Covering Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171203)