General bounds for incremental maximization
From MaRDI portal
Publication:2118105
DOI10.1007/s10107-020-01576-0OpenAlexW3093874042MaRDI QIDQ2118105
Yann Disser, Aaron Bernstein, Martin Groß, Sandra Himburg
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-020-01576-0
greedy algorithmcompetitive analysiscardinality constraintmaximization problemsincremental optimization
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
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
- Online algorithms. The state of the art
- An improved approximation ratio for the minimum latency problem
- Randomized strategies for cardinality robustness in the knapsack problem
- Performance guarantees for hierarchical clustering
- Computing knapsack solutions with cardinality robustness
- Incremental medians via online bidding
- Incremental algorithms for facility location and \(k\)-median
- The minimum latency problem
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
- Note on Independence Functions
- Robbing the bandit
- Incremental flow
- Fast Approximation Algorithms for Knapsack Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- Incremental Clustering and Dynamic Information Retrieval
- The Online Median Problem
- Robust Matchings
- General Bounds for Incremental Maximization
- Robust Randomized Matchings
- Packing a Knapsack of Unknown Capacity
- A General Approach for Incremental Approximation and Hierarchical Clustering
- Greedy in Approximation Algorithms
- Matroids and the greedy algorithm
- Robust Matchings and Matroid Intersections
- Robust Independence Systems
- Approximation algorithms for hierarchical location problems
This page was built for publication: General bounds for incremental maximization