<p><strong>Lemma 1.</strong> <em>The problem is NP-hard.</em></p>
<p><em>Proof.</em> By reduction from Clique.  Given an instance <span class="math-container">$(G=(V,E), k)$</span> of Clique (with <span class="math-container">$k&lt;|V|$</span>), the reduction produces the instance of OP's problem defined as follows.</p>
<ol>
<li><p>Make the number <span class="math-container">$m$</span> of sets to assign to each worker be <span class="math-container">$m={k \choose 2}$</span>.</p>
</li>
<li><p>Take the &quot;budget&quot; for the decision version of the instance of OP's problem to be <span class="math-container">$k$</span>.  (That is, we want the symmetric difference of each workers cache with the union of its assigned sets to have size at most <span class="math-container">$k$</span>.)</p>
</li>
<li><p>Make each vertex <span class="math-container">$v\in V$</span> an object.</p>
</li>
<li><p>For each edge <span class="math-container">$\{u,w\} \in E$</span>, make <span class="math-container">$\{u, w\}$</span> one of the sets of objects.  In addition, repeatedly add the set <span class="math-container">$V,$</span> enough times to make the total number of sets a sufficiently large multiple, say <span class="math-container">$n\times m$</span>, of <span class="math-container">$m$</span>.
(Specifically, take <span class="math-container">$n = \lceil (|E|-1)/(m-1)\rceil$</span> so that
<span class="math-container">$n\times m - |E| \ge n-1$</span>,
then add <span class="math-container">$n\times m - |E|$</span> copies of <span class="math-container">$V$</span>.)</p>
</li>
<li><p>Make <span class="math-container">$n$</span> workers.  Give the first worker an empty initial cache (or fill it with irrelevant artificial objects).  Make the cache of each remaining worker initially contain the set <span class="math-container">$V$</span>.</p>
</li>
</ol>
<p>This completes the reduction.  Next we verify that it is correct.</p>
<hr />
<p>Suppose that <span class="math-container">$G$</span> has a <span class="math-container">$k$</span>-clique <span class="math-container">$C$</span>.
Assign the <span class="math-container">$m={k\choose 2}$</span> edges in <span class="math-container">$C$</span> to the first worker.
To each of the remaining <span class="math-container">$n-1$</span> workers, assign one of the copies of <span class="math-container">$V$</span>.
Assign the remaining <span class="math-container">$m\times n - m - (n-1)$</span> (that is, <span class="math-container">$(m-1)\times (n-1)$</span>) unassigned sets arbitrarily to the <span class="math-container">$n-1$</span> workers other than the first so as to assign <span class="math-container">$m-1$</span> additional sets to each of those workers.</p>
<p>The cost of this assignment is <span class="math-container">$k$</span>.
(Indeed, the size of the symmetric difference for the first worker is <span class="math-container">$k$</span>,
as the union of the edges in the <span class="math-container">$k$</span>-clique contains <span class="math-container">$k$</span> vertices.
For each of the remaining workers, the size of the symmetric difference is zero, as the cache started with <span class="math-container">$V$</span>, and the union of the sets assigned to the worker is <span class="math-container">$V$</span>.)
So, if <span class="math-container">$G$</span> has a <span class="math-container">$k$</span>-clique, then the instance of OP's problem has a solution of cost at most <span class="math-container">$k$</span>.</p>
<hr />
<p>Conversely, suppose the instance of OP's problem has a solution of cost at most <span class="math-container">$k$</span>.  The <span class="math-container">$m={k\choose 2}$</span> sets assigned to the first worker must be edges, because each non-edge set is a copy of <span class="math-container">$V$</span>, and <span class="math-container">$|V| &gt; k$</span>.  The union of those <span class="math-container">${k\choose 2}$</span> edges has size at most <span class="math-container">$k$</span>, so must be the edges of a <span class="math-container">$k$</span>-clique in <span class="math-container">$G$</span>.</p>
<hr />
<p>So the reduction is correct. <span class="math-container">$~~~~\Box$</span>.</p>

CC BY-SA 4.0
2024-04-15T08:47:47.933Z
Great solution that is really inspiring! Can I also use reduction from Set Cover decision problem? For example, assign full cache  for all workers and add −1
 copies of  and some duplicated sets into the original collection of sets to get ∗
 sets. If the minimum of the maximum difference is 0, it means we find a set cover of size .
Han Tian
CC BY-SA 4.0
2024-04-14T18:05:45.820Z
2024-04-14T18:20:31.007Z
2024-04-14T18:20:31.007Z
Neal Young
<p>I am working on a problem where I have <span class="math-container">$n $</span> workers, each with a cache that already contains a specific set of objects. Additionally, I receive <span class="math-container">$n \times m$</span> sets of objects. My task is to assign exactly <span class="math-container">$ m $</span> sets of these objects to each worker, ensuring the assignment is even across all workers. The objective is to minimize the maximum difference between the cache set of any worker and the union of the <span class="math-container">$m$</span> sets assigned to that worker. The &quot;difference&quot; here refers to the symmetric difference between two sets. How can I approach this problem to find the most optimal assignment? Are there existing algorithms or methods that could be adapted to solve this problem efficiently?</p>

CC BY-SA 4.0
2024-04-14T16:39:45.567Z
Closely related: https://cstheory.stackexchange.com/questions/54180/find-the-weighted-perfect-1-to-k-matching-algorithm-with-minimum-aggregated-k ?
Neal Young
CC BY-SA 4.0
2024-04-14T17:05:13.300Z
(i)  What do you mean exactly by "*minimize the ... symmetric difference"* of two sets? The symmetric difference is a set. Do you mean the *size* of the symmetric difference? (ii) Should each of the $n m$ sets be assigned (so the assignment partitions the $n m$ sets into $n$ parts each of size $m$)?  (As opposed to allowing some sets to be assigned multiple times, and others to be unassigned...)
Neal Young
CC BY-SA 4.0
2024-04-15T08:38:35.440Z
@NealYoung (i) Yes the size of the symmetric difference. (ii) Yes.
Han Tian
<graph-algorithms><set-cover>
How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?
Han Tian
# How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

(Asked by: username_0 on 2024-04-14)

I am working on a problem where I have $n $ workers, each with a cache that already contains a specific set of objects. Additionally, I receive $n \times m$ sets of objects. My task is to assign exactly $ m $ sets of these objects to each worker, ensuring the assignment is even across all workers. The objective is to minimize the maximum difference between the cache set of any worker and the union of the $m$ sets assigned to that worker. The "difference" here refers to the symmetric difference between two sets. How can I approach this problem to find the most optimal assignment? Are there existing algorithms or methods that could be adapted to solve this problem efficiently?

**Tags:** graph-algorithms, set-cover
> **Comments:**
> **username_1**: Closely related: https://cstheory.stackexchange.com/questions/54180/find-the-weighted-perfect-1-to-k-matching-algorithm-with-minimum-aggregated-k ?  
> **username_1**: (i)  What do you mean exactly by "*minimize the ... symmetric difference"* of two sets? The symmetric difference is a set. Do you mean the *size* of the symmetric difference? (ii) Should each of the $n m$ sets be assigned (so the assignment partitions the $n m$ sets into $n$ parts each of size $m$)?  (As opposed to allowing some sets to be assigned multiple times, and others to be unassigned...)  
> **username_0**: @NealYoung (i) Yes the size of the symmetric difference. (ii) Yes.  

---

## 1 answers

### Answer by username_1 on 2024-04-14. Score: 1 | Accepted answer

**Lemma 1.** *The problem is NP-hard.*

*Proof.* By reduction from Clique. Given an instance $(G=(V,E), k)$ of Clique (with $k<|V|$), the reduction produces the instance of OP's problem defined as follows.

1. Make the number $m$ of sets to assign to each worker be $m={k \choose 2}$.
2. Take the "budget" for the decision version of the instance of OP's problem to be $k$. (That is, we want the symmetric difference of each workers cache with the union of its assigned sets to have size at most $k$.)
3. Make each vertex $v\in V$ an object.
4. For each edge $\{u,w\} \in E$, make $\{u, w\}$ one of the sets of objects. In addition, repeatedly add the set $V,$ enough times to make the total number of sets a sufficiently large multiple, say $n\times m$, of $m$.
   (Specifically, take $n = \lceil (|E|-1)/(m-1)\rceil$ so that
   $n\times m - |E| \ge n-1$,
   then add $n\times m - |E|$ copies of $V$.)
5. Make $n$ workers. Give the first worker an empty initial cache (or fill it with irrelevant artificial objects). Make the cache of each remaining worker initially contain the set $V$.

This completes the reduction. Next we verify that it is correct.

---

Suppose that $G$ has a $k$-clique $C$.
Assign the $m={k\choose 2}$ edges in $C$ to the first worker.
To each of the remaining $n-1$ workers, assign one of the copies of $V$.
Assign the remaining $m\times n - m - (n-1)$ (that is, $(m-1)\times (n-1)$) unassigned sets arbitrarily to the $n-1$ workers other than the first so as to assign $m-1$ additional sets to each of those workers.

The cost of this assignment is $k$.
(Indeed, the size of the symmetric difference for the first worker is $k$,
as the union of the edges in the $k$-clique contains $k$ vertices.
For each of the remaining workers, the size of the symmetric difference is zero, as the cache started with $V$, and the union of the sets assigned to the worker is $V$.)
So, if $G$ has a $k$-clique, then the instance of OP's problem has a solution of cost at most $k$.

---

Conversely, suppose the instance of OP's problem has a solution of cost at most $k$. The $m={k\choose 2}$ sets assigned to the first worker must be edges, because each non-edge set is a copy of $V$, and $|V| > k$. The union of those ${k\choose 2}$ edges has size at most $k$, so must be the edges of a $k$-clique in $G$.

---

So the reduction is correct. $~~~~\Box$.

> **Comments:**
> **username_0**: Great solution that is really inspiring! Can I also use reduction from Set Cover decision problem? For example, assign full cache  for all workers and add −1  copies of  and some duplicated sets into the original collection of sets to get ∗  sets. If the minimum of the maximum difference is 0, it means we find a set cover of size .  

---

