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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.