Analyzing Residual Random Greedy for monotone submodular maximization

DOI10.1016/j.ipl.2022.106340OpenAlexW4306885005MaRDI QIDQ2680237

Karthekeyan Chandrasekaran, Aditya Pillai, Tamás Király, Kristóf Bérczi

Publication date: 30 January 2023

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

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

zbMATH Keywords

analysis of algorithmssubmodular maximizationmatroid constraintsrandomized greedy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Testing membership in matroid polyhedra
• Iterative Methods in Combinatorial Optimization
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Matroid intersection algorithms
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Submodular Maximization with Cardinality Constraints
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Online submodular maximization: beating 1/2 made simple
• Approximate multi-matroid intersection via iterative refinement

This page was built for publication: Analyzing Residual Random Greedy for monotone submodular maximization