Unified greedy approximability beyond submodular maximization

DOI10.1007/978-3-031-18530-4_22MaRDI QIDQ6166910zbMATH OpenFDO

Authors Y. Disser, David Weckbecker

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation ratioaugmentabilitycardinality-constrained maximizationgreedy algorithmindependence systemsubmodularity ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We consider classes of objective functions of cardinality constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of $gamma$-$alpha$-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, $alpha$-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient - as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of $fracalphagammacdotfracmathrm{e}^{a}lphamathrm{e}^{a}lpha-1$ on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for $alpha$-augmentable functions. In paritcular, as a by-product, we close a gap left in [Math.Prog., 2020] by obtaining a tight lower bound for $alpha$-augmentable functions for all $alphageq1$. For weighted rank functions of independence systems, our tight bound becomes $fracalphagamma$, which recovers the known bound of $1/q$ for independence systems of rank quotient at least $q$.

Recommendations

• Approximation for maximizing monotone non-decreasing set functions with a greedy method
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• Maximize a monotone function with a generic submodularity ratio
• Maximize a monotone function with a generic submodularity ratio
• New performance guarantees for the greedy maximization of submodular set functions

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A THEOREM ON INDEPENDENCE RELATIONS
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Combinatorial optimization. Theory and algorithms.
• General bounds for incremental maximization
• Greedy algorithm and symmetric matroids
• Greedy in Approximation Algorithms
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Matroids and the greedy algorithm
• Maximizing a monotone submodular function subject to a matroid constraint
• Non-monotone submodular maximization under matroid and knapsack constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Robust monotone submodular function maximization
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• 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
• The design of approximation algorithms
• Unified greedy approximability beyond submodular maximization

Cited in

(4)

• A refined analysis of submodular greedy
• Unified Greedy Approximability beyond Submodular Maximization
• Unified greedy approximability beyond submodular maximization
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows

This page was built for publication: Unified greedy approximability beyond submodular maximization

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