.png){kind=icon}
返回
Online vector scheduling and generalized load balancing
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2013.12.006.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We give a polynomial time reduction from the vector scheduling problem (VS) to the generalized load balancing problem (GLB). This reduction gives the first non-trivial online algorithm for VS where vectors come in an online fashion. The online algorithm is very simple in that each vector only needs to minimize the L-ln(md) norm of the resulting load when it comes, where m is the number of partitions and d is the dimension of vectors. It has an approximation bound of e log(md), which is in O(ln(md)), so it also improves the O(ln(2) d) bound of the existing polynomial time algorithm for VS. Additionally, the reduction shows that GLB does not have constant approximation algorithms that run in polynomial time unless P = NP. (C) 2013 Elsevier Inc. All rights reserved.
Keyword:
Online algorithm
Vector scheduling
Load balancing
Approximation algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
.png){kind=icon}
分享收藏