Submodular Optimization with Contention Resolution Extensions.

DOI10.4230/LIPICS.APPROX-RANDOM.2019.3MaRDI QIDQ5875454zbMATH OpenOpenAlexFDO

Authors Benjamin Moseley, Maxim Sviridenko

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.3

zbMATH Keywords

optimizationapproximation algorithminterval schedulingsubmodular

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Constrained submodular maximization via a nonsymmetric technique
• Maximizing Non-monotone Submodular Functions
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• On multiplicative weight updates for concave and submodular function maximization
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular maximization over multiple matroids via generalized exchange properties
• Symmetry and approximability of submodular maximization problems

Cited in

(2)

• Submodular containment is hard, even for networks
• Submodular Cost Allocation Problem and Applications

This page was built for publication: Submodular Optimization with Contention Resolution Extensions.

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