<p>This is the <strong>Vector Scheduling</strong> (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input: </p>

<p>Chekuri, C., Khanna, S.: On multidimensional packing problems.
<em>SIAM J. Comput.</em>, 33(4):837-851, 2004. </p>

<p>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:</p>

<p>Bansal, N., Vredeveld, T., van der Zwaan, R.: Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. <em>Lecture Notes in Computer Science</em>, 8392:47-59, 2014. </p>

CC BY-SA 3.0
2014-04-02T23:52:17.073Z
2014-04-02T23:52:17.073Z
Vincenzo
<p>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.</p>

<p>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? </p>

<approximation-algorithms><scheduling><approximation>
Minimize makespan on identical machines when jobs are vectors
vikram
# Minimize makespan on identical machines when jobs are vectors

(Asked by: username_0 on 2014-04-02)

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?

**Tags:** approximation-algorithms, scheduling, approximation


---

## 1 answers

### Answer by username_1 on 2014-04-02. Score: 5

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.


---

