Submodular function minimization under a submodular set covering constraint

DOI10.1007/978-3-642-20877-5_14MaRDI QIDQ3010395zbMATH OpenOpenAlexFDO

Authors Naoyuki Kamiyama

Publication date 1 July 2011

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

Full work available at URL https://doi.org/10.1007/978-3-642-20877-5_14

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Submodular function minimization with submodular set covering constraints and precedence constraints
• A note on submodular function minimization with covering type linear constraints
• Maximizing submodular set functions subject to multiple linear constraints
• On minimum submodular cover with submodular cost
• A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

Cites work

• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A faster strongly polynomial time algorithm for submodular function minimization
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Discrete Convex Analysis
• Geometric algorithms and combinatorial optimization
• On approximation of the submodular set cover problem
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular Function Minimization under Covering Constraints
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(12)

• Active-set Methods for Submodular Minimization Problems
• Submodular function minimization
• On minimum submodular cover with submodular cost
• An approximation algorithm and its performance guarantee for minimizing non-decreasing supermodular set function
• A note on submodular function minimization with covering type linear constraints
• Submodular Maximization With Limited Function Access
• Submodular function minimization with submodular set covering constraints and precedence constraints
• Minimum non-submodular cover problem with applications
• Complexity and approximations for submodular minimization problems on two variables per inequality constraints
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Minimization problems with non-submodular cover constraint
• A note on submodular set cover on matroids

This page was built for publication: Submodular function minimization under a submodular set covering constraint

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