Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint

DOI10.1016/J.IPL.2016.04.004zbMath1358.68320OpenAlexW2188142085MaRDI QIDQ284354

Kaito Fujii

Publication date: 18 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.04.004

zbMATH Keywords

submodular functionapproximation algorithms\(b\)-matching

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple approximation algorithm for the weighted matching problem
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Combinatorial auctions with decreasing marginal utilities
• Improved Approximations for k-Exchange Systems
• A threshold of ln n for approximating set cover
• Linear-Time Approximation for Maximum Weight Matching
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Fast algorithms for maximizing submodular functions
• Greedy in Approximation Algorithms
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint