Improved algorithms for online load balancing

DOI10.1007/978-3-030-67731-2_15MaRDI QIDQ831807zbMATH OpenOpenAlexFDO

Authors Yaxiong Liu, Kohei Hatano, Eiji Takimoto

Publication date 24 March 2022

Full work available at URL https://arxiv.org/abs/2007.07515, http://hdl.handle.net/2324/4495597

zbMATH Keywords

makespanonline learningsecond-order cone programmingonline load balancingBlackwell approachability

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Multistage and repeated games (91A20)

Abstract: We consider an online load balancing problem and its extensions in the framework of repeated games. On each round, the player chooses a distribution (task allocation) over $K$ servers, and then the environment reveals the load of each server, which determines the computation time of each server for processing the task assigned. After all rounds, the cost of the player is measured by some norm of the cumulative computation-time vector. The cost is the makespan if the norm is $L_{i}nfty$-norm. The goal is to minimize the regret, i.e., minimizing the player's cost relative to the cost of the best fixed distribution in hindsight. We propose algorithms for general norms and prove their regret bounds. In particular, for $L_{i}nfty$-norm, our regret bound matches the best known bound and the proposed algorithm runs in polynomial time per trial involving linear programming and second order programming, whereas no polynomial time algorithm was previously known to achieve the bound.

Recommendations

• Ancient and new algorithms for load balancing in the \(\ell_p\) norm
• On-line load balancing
• Online and Random-order Load Balancing Simultaneously
• Load balancing without regret in the bulletin board model
• Load balancing without regret in the bulletin board model

Cites work

• An analog of the minimax theorem for vector payoffs
• An online convex optimization approach to Blackwell's approachability
• Applications of second-order cone programming
• Exponentiated gradient versus gradient descent for linear predictors
• On-line load balancing made simple: greedy strikes back
• Online and Random-order Load Balancing Simultaneously
• Online learning and online convex optimization
• Online load balancing of temporary tasks

Cited in

(3)

• scientific article; zbMATH DE number 7626715 (Why is no real title available?)
• Load balancing without regret in the bulletin board model
• Load balancing without regret in the bulletin board model

This page was built for publication: Improved algorithms for online load balancing

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