Towards nearly-linear time algorithms for submodular maximization with a matroid constraint

DOI10.4230/LIPICS.ICALP.2019.54MaRDI QIDQ5091209zbMATH OpenFDO

Authors

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1811.07464

zbMATH Keywords

submodular maximizationmatroid constraintsfast running times

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Fast algorithms for maximizing submodular functions
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Fast algorithms for maximizing monotone nonsubmodular functions
• Non-monotone submodular maximization under matroid and knapsack constraints

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• An improved equivalence algorithm
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Fast algorithms for maximizing submodular functions
• Maximizing a monotone submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• On multiplicative weight updates for concave and submodular function maximization
• Optimal approximation for the submodular welfare problem in the value oracle model
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Revenue submodularity
• Submodular maximization with cardinality constraints

Cited in

(5)

• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Approximation guarantees for deterministic maximization of submodular function with a matroid constraint

This page was built for publication: Towards nearly-linear time algorithms for submodular maximization with a matroid constraint

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