Unified greedy approximability beyond submodular maximization

DOI10.1007/978-3-031-18530-4_22zbMath1528.90214arXiv2011.00962MaRDI QIDQ6166910

David Weckbecker, Yann Disser

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

greedy algorithmindependence systemapproximation ratioaugmentabilitysubmodularity ratiocardinality-constrained maximization

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A note on maximizing a submodular set function subject to a knapsack constraint
• Robust monotone submodular function maximization
• General bounds for incremental maximization
• The Design of Approximation Algorithms
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Greedy algorithm and symmetric matroids
• An analysis of approximations for maximizing submodular set functions—I
• An Analysis of the Greedy Heuristic for Independence Systems
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular Maximization with Cardinality Constraints
• Greedy in Approximation Algorithms
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Matroids and the greedy algorithm
• A THEOREM ON INDEPENDENCE RELATIONS
• Combinatorial optimization. Theory and algorithms.
• Unified greedy approximability beyond submodular maximization

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