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

DOI10.4230/LIPICS.ICALP.2019.54MaRDI QIDQ5091209FDOQ5091209

Authors:

Publication date: 21 July 2022

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

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

zbMATH Keywords

submodular maximizationmatroid constraintsfast running times

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• 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)