Robust online algorithms for dynamic choosing problems

DOI10.1007/978-3-030-80049-9_4OpenAlexW3183133566MaRDI QIDQ2117763

Sebastian Berndt, Lukas Johannsen, Klaus Jansen, Kilian Grage, Maria Kosche

Publication date: 22 March 2022

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

zbMATH Keywords

migrationonline algorithmscompetitive ratioknapsackdynamic algorithmsmaximum independent set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust algorithms for preemptive scheduling
• A robust APTAS for the classical bin packing problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Robust online algorithms for certain dynamic packing problems
• Fully dynamic bin packing revisited
• The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
• Robust Approximation Schemes for Cube Packing
• A survey on combinatorial optimization in dynamic environments
• The Power of Dynamic Distance Oracles
• Online Scheduling with Bounded Migration
• Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
• Online and dynamic algorithms for set cover
• Fully-Dynamic Bin Packing with Little Repacking
• Symmetry exploitation for online machine covering with bounded migration
• Online Bin Covering with Limited Migration
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• The State of the Art in Dynamic Graph Algorithms
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• A Robust AFPTAS for Online Bin Packing with Polynomial Migration,
• Approximation algorithms for maximum independent set of pseudo-disks

This page was built for publication: Robust online algorithms for dynamic choosing problems