Relaxing the irrevocability requirement for online graph algorithms

DOI10.1007/s00453-022-00944-wzbMath1492.68145arXiv1704.08835OpenAlexW2952999756MaRDI QIDQ5918715

Michal Kotrbčík, Lene Monrad Favrholdt, Kim S. Larsen, Joan. Boyar

Publication date: 28 June 2022

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

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

zbMATH Keywords

competitive analysisonline algorithmsgraph algorithmspreemptionrecourse

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Online maximum matching with recourse ⋮ The power of amortized recourse for online graph problems ⋮ Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems ⋮ Online knapsack with removal and recourse ⋮ Online Maximum Matching with Recourse ⋮ Relaxing the irrevocability requirement for online graph algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online knapsack revisited
• Randomized algorithms for online knapsack problems
• Online minimization knapsack problem
• Competitive snoopy caching
• Online dominating set
• On-line vertex-covering
• Online removable knapsack problem under convex function
• On graph problems in a semi-streaming model
• A linear-time approximation algorithm for weighted matchings in graphs
• The Frequent Items Problem in Online Streaming Under Various Performance Measures
• Improved Bounds for Online Preemptive Matching
• Efficient On-Line Call Control Algorithms
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
• Kuratowski's theorem
• Dynamic Steiner Tree Problem
• An Analysis of the Greedy Heuristic for Independence Systems
• Online Budgeted Maximum Coverage
• Advice Complexity of the Online Induced Subgraph Problem
• Online traveling salesman problems with rejection options
• On the Abstract Properties of Linear Dependence
• Online Maximum Matching with Recourse
• Online Submodular Maximization with Preemption
• Online Steiner Tree with Deletions
• The Power of Recourse for Online MST and TSP
• Relaxing the irrevocability requirement for online graph algorithms
• On the Advice Complexity of Online Edge- and Node-Deletion Problems

This page was built for publication: Relaxing the irrevocability requirement for online graph algorithms