General bounds for incremental maximization

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

zbMATH Keywords

greedy algorithmcompetitive analysiscardinality constraintmaximization problemsincremental optimization

Mathematics Subject Classification ID

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