Analyzing Residual Random Greedy for monotone submodular maximization

DOI10.1016/J.IPL.2022.106340MaRDI QIDQ2680237zbMATH OpenOpenAlexFDO

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

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 algorithmsmatroid constraintsrandomized greedysubmodular maximization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
• An analysis of approximations for maximizing submodular set functions—I
• Approximate multi-matroid intersection via iterative refinement
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Connections in combinatorial optimization
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• Iterative methods in combinatorial optimization.
• Matroid intersection algorithms
• Maximizing a monotone submodular function subject to a matroid constraint
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular maximization with cardinality constraints
• 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

Cited in

(1)

• A refined analysis of submodular greedy

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

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