Online vector scheduling and generalized load balancing |
| |
Authors: | Xiaojun Zhu Qun Li Weizhen Mao Guihai Chen |
| |
Affiliation: | 1. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;2. Department of Computer Science, College of William and Mary, Williamsburg, Virginia 23187, USA;3. Shanghai Key Laboratory of Scalable Computing and Systems, Shanghai Jiao Tong University, Shanghai 200240, China |
| |
Abstract: | 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 Lln(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 elog(md), which is in O(ln(md)), so it also improves the O(ln2d) 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. |
| |
Keywords: | Online algorithm Vector scheduling Load balancing Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|