Robust online algorithms for dynamic choosing problems

DOI10.1007/978-3-030-80049-9_4MaRDI QIDQ2117763zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

online algorithmscompetitive ratiomigrationmaximum independent setknapsackdynamic algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

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

Cited in

(1)

• scientific article; zbMATH DE number 437568 (Why is no real title available?)

Describes a project that uses

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)