Robust online algorithms for dynamic choosing problems

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

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

Publication date: 22 March 2022

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

Recommendations

• Robust online algorithms for certain dynamic packing problems
• Online bin covering with limited migration
• On-line bin packing with restricted repacking
• Online knapsack revisited
• Algorithms for the on-line bin packing problem with repacking

zbMATH Keywords

online algorithmscompetitive ratiomigrationmaximum independent setknapsackdynamic algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Fully dynamic bin packing revisited
• Fully-dynamic bin packing with little repacking
• Approximation algorithms for knapsack problems with cardinality constraints
• A robust APTAS for the classical bin packing problem
• A survey on combinatorial optimization in dynamic environments
• Approximation algorithms for maximum independent set of pseudo-disks
• The maximum edge-disjoint paths problem in bidirected trees
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Title not available (Why is that?)
• Online and dynamic algorithms for set cover
• Online scheduling with bounded migration
• Robust approximation schemes for cube packing
• Robust algorithms for preemptive scheduling
• A robust AFPTAS for online bin packing with polynomial migration
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Online strip packing with polynomial migration
• The State of the Art in Dynamic Graph Algorithms
• The Power of Dynamic Distance Oracles
• Symmetry exploitation for online machine covering with bounded migration
• Online Bin Covering with Limited Migration
• Robust online algorithms for certain dynamic packing problems
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

Cited In (1)

• Title not available (Why is that?)

Uses Software

• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117763)