Submodular Function Minimization under a Submodular Set Covering Constraint

DOI10.1007/978-3-642-20877-5_14zbMath1332.90225OpenAlexW1584623429MaRDI QIDQ3010395

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)

Related Items (2)

A note on submodular function minimization with covering type linear constraints ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

Cites Work

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

This page was built for publication: Submodular Function Minimization under a Submodular Set Covering Constraint