Online and Random-order Load Balancing Simultaneously

DOI10.1137/1.9781611974782.108MaRDI QIDQ4575851zbMATH OpenOpenAlexFDO

Authors Marco Molinaro

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Abstract: We consider the problem of online load balancing under lp-norms: sequential jobs need to be assigned to one of the machines and the goal is to minimize the lp-norm of the machine loads. This generalizes the classical problem of scheduling for makespan minimization (case l_infty) and has been thoroughly studied. However, despite the recent push for beyond worst-case analyses, no such results are known for this problem. In this paper we provide algorithms with simultaneous guarantees for the worst-case model as well as for the random-order (i.e. secretary) model, where an arbitrary set of jobs comes in random order. First, we show that the greedy algorithm (with restart), known to have optimal O(p) worst-case guarantee, also has a (typically) improved random-order guarantee. However, the behavior of this algorithm in the random-order model degrades with p. We then propose algorithm SIMULTANEOUSLB that has simultaneously optimal guarantees (within constants) in both worst-case and random-order models. In particular, the random-order guarantee of SIMULTANEOUSLB improves as p increases. One of the main components is a new algorithm with improved regret for Online Linear Optimization (OLO) over the non-negative vectors in the lq ball. Interestingly, this OLO algorithm is also used to prove a purely probabilistic inequality that controls the correlations arising in the random-order model, a common source of difficulty for the analysis. Another important component used in both SIMULTANEOUSLB and our OLO algorithm is a smoothing of the lp-norm that may be of independent interest. This smoothness property allows us to see algorithm SIMULTANEOUSLB as essentially a greedy one in the worst-case model and as a primal-dual one in the random-order model, which is instrumental for its simultaneous guarantees.

Recommendations

• Online multidimensional load balancing
• Randomized algorithms for online vector load balancing
• scientific article; zbMATH DE number 1256657
• On-line load balancing
• Parallel randomized load balancing
• Dynamic load balancing by random matchings
• Online load balancing with general reassignment cost
• Improved bounds for on-line load balancing
• On-line load balancing and network flow

Cited in

(14)

• Scheduling In the random-order model
• Improved online algorithms for knapsack and GAP in the random order model
• Online load balancing with general reassignment cost
• On-Line Load Balancing of Temporary Tasks
• scientific article; zbMATH DE number 7626715 (Why is no real title available?)
• Online load balancing of temporary tasks
• Stochastic _p load balancing and moment problems via the L-function method
• Well-behaved online load balancing against strategic jobs
• Machine covering in the random-order model
• Online load balancing on uniform machines with limited migration
• A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
• Knapsack secretary with bursty adversary
• Scheduling in the random-order model
• Improved algorithms for online load balancing

This page was built for publication: Online and Random-order Load Balancing Simultaneously

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