0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Closely related: cstheory.stackexchange.com/questions/54180/… ? $\endgroup$
    – Neal Young
    Commented Apr 14 at 16:39
  • $\begingroup$ (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...) $\endgroup$
    – Neal Young
    Commented Apr 14 at 17:05
  • $\begingroup$ @NealYoung (i) Yes the size of the symmetric difference. (ii) Yes. $\endgroup$
    – Han Tian
    Commented Apr 15 at 8:38

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 π‘š. $\endgroup$
    – Han Tian
    Commented Apr 15 at 8:47

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.