Online load balancing with general reassignment cost

DOI10.1016/J.ORL.2022.03.007MaRDI QIDQ2157902zbMATH OpenOpenAlexFDO

Authors Sebastian Berndt, Franziska Eberle, Nicole Megow

Publication date 22 July 2022

Published in Operations Research Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.orl.2022.03.007

zbMATH Keywords

competitive analysismigrationrecourseonline load balancing

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• scientific article; zbMATH DE number 1256657
• Online and Random-order Load Balancing Simultaneously
• Online multidimensional load balancing
• On-line load balancing
• Improved bounds for on-line load balancing
• Online load balancing on uniform machines with limited migration
• Online vector scheduling and generalized load balancing
• On-line load balancing and network flow
• On-line load balancing made simple: greedy strikes back
• Well-behaved online load balancing against strategic jobs

Cites work

• scientific article; zbMATH DE number 742966 (Why is no real title available?)
• scientific article; zbMATH DE number 7758339 (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
• Better Bounds for Online Scheduling
• Competitive routing of virtual circuits with unknown duration
• Concentration of Measure for the Analysis of Randomized Algorithms
• Dynamic Steiner Tree Problem
• Fully dynamic bin packing revisited
• Fully-dynamic bin packing with little repacking
• Improved Bounds for the Online Scheduling Problem
• Improved bounds for on-line load balancing
• Load Balancing for Response Time
• Maintaining assignments online: matching, scheduling, and flows
• Network flows. Theory, algorithms, and applications.
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Online and dynamic algorithms for set cover
• Online bipartite matching with amortized \(O(\log^2 n)\) replacements
• Online maximum matching with recourse
• Online scheduling with bounded migration
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Robust algorithms for preemptive scheduling
• Robust approximation schemes for cube packing
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Simultaneously load balancing for every \(p\)-norm, with reassignments
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP

Cited in

(5)

• Well-behaved online load balancing against strategic jobs
• Online load balancing on uniform machines with limited migration
• Improved bounds for on-line load balancing
• Online unrelated-machine load balancing and generalized flow with recourse
• Online and Random-order Load Balancing Simultaneously

This page was built for publication: Online load balancing with general reassignment cost

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