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

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

Cited in

(41)

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

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)