Incremental-decremental maximization

DOI10.1007/978-3-032-06706-7_7MaRDI QIDQ6860273zbMATH OpenFDO

Authors Y. Disser, Max Klimm, Annette Lutz, Lea Strubberg

Publication date 10 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-06706-7_7

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25)

Cites work

• A threshold of ln n for approximating set cover
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An analysis of approximations for maximizing submodular set functions—I
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Approximating incremental combinatorial optimization problems
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• General bounds for incremental maximization
• Gross substitutability: an algorithmic survey
• Incremental maximization via continuization
• Job Matching, Coalition Formation, and Gross Substitutes
• Maximize a monotone function with a generic submodularity ratio
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Unified Greedy Approximability beyond Submodular Maximization

This page was built for publication: Incremental-decremental maximization

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