<p>I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of the $k$ programs on the same number of machines, that part is easy. </p>

<p>My problem is how can I do that while minimizing the number of machines having any 2 programs installed. In other words, if I run 2 of those programs, I want to avoid having them run on the same set of machines while some other machines in the cluster are doing nothing.</p>

<p>In terms of sets, the questions becomes how to find $k$ subsets of a set of $N$ elements such that </p>

<ol>
<li>any element is in $p$ subsets and</li>
<li>the maximum size of the intersection of any 2 subsets is minimized.</li>
</ol>

<p>Any pointers / heuristic approach is appreciated.</p>

CC BY-SA 3.0
2015-09-21T21:04:49.623Z
It looks to me like you're looking for something related to [BIBDs](https://en.wikipedia.org/wiki/Block_design#Definition_of_a_BIBD_.28or_2-design.29).
mhum
<set-cover>
Optimizing distribution of load
Thomas Materna
# Optimizing distribution of load

(Asked by: username_0 on 2015-09-21)

I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of the $k$ programs on the same number of machines, that part is easy.

My problem is how can I do that while minimizing the number of machines having any 2 programs installed. In other words, if I run 2 of those programs, I want to avoid having them run on the same set of machines while some other machines in the cluster are doing nothing.

In terms of sets, the questions becomes how to find $k$ subsets of a set of $N$ elements such that

1. any element is in $p$ subsets and
2. the maximum size of the intersection of any 2 subsets is minimized.

Any pointers / heuristic approach is appreciated.

**Tags:** set-cover
> **Comments:**
> **username_1**: It looks to me like you're looking for something related to [BIBDs](https://en.wikipedia.org/wiki/Block_design#Definition_of_a_BIBD_.28or_2-design.29).  

---

## 0 answers

