<p>Appreciable literature is available in this standard book on Approximation Algo by Vazirani
<a href="http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf" rel="nofollow">http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf</a></p>

<p>Refer to chapter 10 for details.</p>

CC BY-SA 3.0
2014-06-26T18:31:40.090Z
I don't think this problem has that much of a connection to makespan. Here there is no constraint at all on the load to machines.
Sasho Nikolov
CC BY-SA 3.0
2014-06-26T20:34:20.053Z
@SashoNikolov The objective function is basically a makespan constraint over $k$ dimensions. This is related to vector scheduling where each job has $k$ dimensions.
Chandra Chekuri
CC BY-SA 3.0
2014-06-26T22:27:53.953Z
@ChandraChekuri I disagree (or I may be missing something). What I would call a makespan problem would have the constraint $\forall j: \max_{k} \sum_i{x_{ij}c_{ijk}} \leq T$ and the objective would be to minimize $T$. Right now there are no constraints on machines, and the minimization is for the total cost.
Sasho Nikolov
CC BY-SA 3.0
2014-06-27T01:47:20.763Z
@SashoNikolov the question is ill phrased I think. I looked at the refs and figured it was the multidimensional/vector scheduling problem.
Chandra Chekuri
CC BY-SA 3.0
2014-06-27T03:25:49.697Z
@ChandraChekuri I was wrong in my previous comment (now deleted). I think the problem makes sense actually, and I can see that it generalizes scheduling on unrelated machines. But this is if you think of the third dimensions as the machines, and $c_{ijk}$ is nonzero only for $k=j$. So this problem minimizes the maximum load per resource ("makespan over resources"), even though it sums each resource over machines. To OP: you can also check Chapter 11.1 of the Williamson-Shmoys book, and also 16.1. for a hardness reduction http://www.designofapproxalgs.com/book.pdf
Sasho Nikolov
CC BY-SA 3.0
2014-05-27T09:14:38.557Z
2014-05-27T09:14:38.557Z
sbzk
<p>i am looking for literature on this kind of problem.
$$
\begin{align}
\min_x \max_k &amp;\quad \sum_{i,j} x_{ij}c_{ijk}\\
\text{subject to}&amp;\\
&amp;\sum_j x_{ij}=1,&amp;&amp; \forall i\in\mathcal J\\
&amp;x_{ij}\in\{0,1\},&amp;&amp; \forall i\in\mathcal J, j\in\mathcal M
\end{align}
$$</p>

<ul>
<li>$\mathcal J$ is a set of Jobs and $\mathcal M$ is a set of Machines.</li>
<li>$c_{ij}$ is a vector and describes the cost of the job $i$ on the machine $j$.
So the cost has multiple dimension.</li>
</ul>

<p>The Aim of the programm is to find a schedule so that each job is scheduled on a machine and the biggest dimension of the add up cost vector is minimized. </p>

<p>The problem is described here:</p>

<p><a href="http://arxiv.org/pdf/1211.5729v2.pdf" rel="nofollow">http://arxiv.org/pdf/1211.5729v2.pdf</a> (Page 2 left column bottom) as Generalized load balancing</p>

<p>and here:</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&amp;rep=rep1&amp;type=pdf</a> (Page 4 left column) as  generalized AP association
problem</p>

<p><strong>EDIT</strong></p>

<p>load balancing can be generalized in several ways, i.e. restrict that each job can only run on a specific set of machines. 
This is also a generalization of the scheduling problem.</p>

<p>I'm interested in the case where the scheduling is restricted and multidimensional.
I'm looking for more literature for this problem.</p>

<p>Thank you</p>

CC BY-SA 3.0
2014-06-26T18:32:15.753Z
When $k=1$ this is just the classical assignment problem (which can be solved optimally in poly time). This is essentially asking to find a single solution to the assignment problem which has low cost for all $k$ instances simultaneously.
Sasho Nikolov
CC BY-SA 3.0
2014-06-26T19:23:49.613Z
One can get an $O(\log k/\log \log k)$-approximation for this problem. Look at a recent Arxiv paper below and references in that paper. http://arxiv.org/pdf/1406.5943v1.pdf
Chandra Chekuri
<ds.algorithms><reference-request><co.combinatorics><linear-programming><heuristics>
Literature for Generalized Load Balancing
AppleTree
# Literature for Generalized Load Balancing

(Asked by: username_0 on 2014-05-19)

i am looking for literature on this kind of problem.
$$
\begin{align}
\min\_x \max\_k &\quad \sum\_{i,j} x\_{ij}c\_{ijk}\\
\text{subject to}&\\
&\sum\_j x\_{ij}=1,&& \forall i\in\mathcal J\\
&x\_{ij}\in\{0,1\},&& \forall i\in\mathcal J, j\in\mathcal M
\end{align}
$$

* $\mathcal J$ is a set of Jobs and $\mathcal M$ is a set of Machines.
* $c\_{ij}$ is a vector and describes the cost of the job $i$ on the machine $j$.
  So the cost has multiple dimension.

The Aim of the programm is to find a schedule so that each job is scheduled on a machine and the biggest dimension of the add up cost vector is minimized.

The problem is described here:

<http://arxiv.org/pdf/1211.5729v2.pdf> (Page 2 left column bottom) as Generalized load balancing

and here:

<http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&rep=rep1&type=pdf> (Page 4 left column) as generalized AP association
problem

**EDIT**

load balancing can be generalized in several ways, i.e. restrict that each job can only run on a specific set of machines.
This is also a generalization of the scheduling problem.

I'm interested in the case where the scheduling is restricted and multidimensional.
I'm looking for more literature for this problem.

Thank you

**Tags:** ds.algorithms, reference-request, co.combinatorics, linear-programming, heuristics
> **Comments:**
> **username_1**: When $k=1$ this is just the classical assignment problem (which can be solved optimally in poly time). This is essentially asking to find a single solution to the assignment problem which has low cost for all $k$ instances simultaneously.  
> **username_2**: One can get an $O(\log k/\log \log k)$-approximation for this problem. Look at a recent Arxiv paper below and references in that paper. http://arxiv.org/pdf/1406.5943v1.pdf  

---

## 1 answers

### Answer by username_3 on 2014-05-27. Score: 1

Appreciable literature is available in this standard book on Approximation Algo by Vazirani
<http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf>

Refer to chapter 10 for details.

> **Comments:**
> **username_1**: I don't think this problem has that much of a connection to makespan. Here there is no constraint at all on the load to machines.  
> **username_2**: @SashoNikolov The objective function is basically a makespan constraint over $k$ dimensions. This is related to vector scheduling where each job has $k$ dimensions.  
> **username_1**: @ChandraChekuri I disagree (or I may be missing something). What I would call a makespan problem would have the constraint $\forall j: \max_{k} \sum_i{x_{ij}c_{ijk}} \leq T$ and the objective would be to minimize $T$. Right now there are no constraints on machines, and the minimization is for the total cost.  
> **username_2**: @SashoNikolov the question is ill phrased I think. I looked at the refs and figured it was the multidimensional/vector scheduling problem.  
> **username_1**: @ChandraChekuri I was wrong in my previous comment (now deleted). I think the problem makes sense actually, and I can see that it generalizes scheduling on unrelated machines. But this is if you think of the third dimensions as the machines, and $c_{ijk}$ is nonzero only for $k=j$. So this problem minimizes the maximum load per resource ("makespan over resources"), even though it sums each resource over machines. To OP: you can also check Chapter 11.1 of the Williamson-Shmoys book, and also 16.1. for a hardness reduction http://www.designofapproxalgs.com/book.pdf  

---

