Submodular Function Minimization under Covering Constraints
From MaRDI portal
Publication:5171203
DOI10.1109/FOCS.2009.31zbMath1292.68168MaRDI QIDQ5171203
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Related Items (36)
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ An approximation algorithm for submodular hitting set problem with linear penalties ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem ⋮ Minimum hitting set of interval bundles problem: computational complexity and approximability ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Equivalence of convex minimization problems over base polytopes ⋮ Algorithms for maximizing monotone submodular function minus modular function under noise ⋮ Generalized roof duality and bisubmodular functions ⋮ The multi-budget maximum weighted coverage problem ⋮ Approximability of sparse integer programs ⋮ Unnamed Item ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ LP-based covering games with low price of anarchy ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Submodular Cost Allocation Problem and Applications ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ 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 ⋮ Robust budget allocation via continuous submodular functions ⋮ A note on submodular function minimization with covering type linear constraints ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ A note on the submodular vertex cover problem with submodular penalties ⋮ Approximation algorithm for stochastic set cover problem ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ Algorithm 996 ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties ⋮ New approximations and hardness results for submodular partitioning problems
This page was built for publication: Submodular Function Minimization under Covering Constraints
