How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

Question

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?

Answer 1

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$.