Online vector scheduling and generalized load balancing

• We prove that vector scheduling is a special case of generalized load balancing.
• We give the first non-trivial online algorithm for vector scheduling based on the proof.
• We show that generalized load balancing does not admit constant approximation algorithms unless P=NPP=NP.

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)Lln(md) norm of the resulting load when it comes, where mm is the number of partitions and dd is the dimension of vectors. It has an approximation bound of elog(md)elog(md), which is in O(ln(md))O(ln(md)), so it also improves the O(ln2d)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=NPP=NP.