Improved Algorithms for Online Load Balancing

• Item type: SIG Technical Reports(1)
• 公開日: 2019-09-10
• タイトル: Improved Algorithms for Online Load Balancing
• タイトル / 言語: en
• タイトル: Improved Algorithms for Online Load Balancing
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Informatics, Kyushu University／RIKEN AIP
• 著者所属: Faculty of Arts and Science, Kyushu University／RIKEN AIP
• 著者所属: Department of Informatics, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University / RIKEN AIP
• 著者所属(英): en
• 著者所属(英): Faculty of Arts and Science, Kyushu University / RIKEN AIP
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University
• 著者名: Yaxiong, Liu; Kohei, Hatano; Eiji, Takimoto
• 著者名(英): Yaxiong, Liu; Kohei, Hatano; Eiji, Takimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We construct algorithms for online load balancing and its extension in the framework of online learning. On each round a player predicts a distribution over K-machines. Then the player receives the true load of each machine. The cost incurred by the player is the p-norm (if p = ∞, the makespan) of the cumulative load vector. Our algorithms achieve the best known bound for p = ∞ and an improved bound for p > 2. In particular, our algorithm for the online load balancing involves linear programming and second order cone programming, which are solved in polynomial time.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We construct algorithms for online load balancing and its extension in the framework of online learning. On each round a player predicts a distribution over K-machines. Then the player receives the true load of each machine. The cost incurred by the player is the p-norm (if p = ∞, the makespan) of the cumulative load vector. Our algorithms achieve the best known bound for p = ∞ and an improved bound for p > 2. In particular, our algorithm for the online load balancing involves linear programming and second order cone programming, which are solved in polynomial time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-174, 号 3, p. 1-7, 発行日 2019-09-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会