Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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:
Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004.
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:
Bansal, N., Vredeveld, T., van der Zwaan, R.: Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Lecture Notes in Computer Science, 8392:47-59, 2014.
