# Minimize makespan on identical machines when jobs are vectors

Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the component-wise sum is minimized over all machines.

I would like to know is there any constant factor approximation algorithm for this problem and is there a generalization of list scheduling to this problem, if so what is its worst-case ratio?

This is the Vector Scheduling (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input:
The same paper gives a polynomial-time approximation scheme when $d$ is not part of the input, and a polynomial time $O((\log d)^2)$ approximation when $d$ is part of the input. The latter was improved to $O(\log d)$ by Meyerson, Roytman and Tagiku (APPROX 2013). For more references and recent results you can refer to: