<p>The problem is hard if <span class="math-container">$k$</span> is part of the input (not fixed):</p>
<p><strong>Lemma 1.</strong> <em>The problem is NP-hard, even for <span class="math-container">$n=2$</span>.</em></p>
<p>The problem is also hard if <span class="math-container">$k$</span> (but not <span class="math-container">$n$</span>) is fixed (with <span class="math-container">$k\ge 3$</span>):</p>
<p><strong>Lemma 2.</strong> <em>The problem is strongly NP-hard, even for <span class="math-container">$k=3$</span>.</em></p>
<p>The problem is in P if <span class="math-container">$k=1$</span> or <span class="math-container">$n=1$</span>:</p>
<p><strong>Lemma 3.</strong> <em>The problem is in P for <span class="math-container">$k=1$</span> or <span class="math-container">$n=1$</span>.</em></p>
<p><strong>We leave open whether the problem is NP-hard for <span class="math-container">$k=2$</span>.</strong></p>
<hr />
<p><em>Proof of Lemma 1.</em> The proof is by reduction from the NP-hard <a href="https://en.wikipedia.org/wiki/Balanced_number_partitioning#Two-way_balanced_partitioning" rel="nofollow noreferrer">Two-Way Balanced Partition</a> problem.
Fix an instance <span class="math-container">$x \in \mathbb N^{2n'}$</span> of Two-Way Balanced Partition.
The goal is to determine whether there is a subset <span class="math-container">$S\subseteq [2n']$</span>
of size <span class="math-container">$n'$</span>
such that <span class="math-container">$\sum_{j\in S} x_j = \lambda$</span>,
where <span class="math-container">$\lambda = \sum_{j=1}^{2n'} x_j / 2$</span>.
Given <span class="math-container">$x$</span>, the reduction outputs the instance <span class="math-container">$(n, k, w, \lambda)$</span> of the decision version of OP's problem
<span class="math-container">$n=2$</span>, <span class="math-container">$k=n'$</span>, and <span class="math-container">$w_{ij} = x_j$</span>
for <span class="math-container">$(i, j) \in [2]\times [2n']$</span>.</p>
<p>Next we verify that the reduction is correct.
Suppose that there is a feasible subset <span class="math-container">$S$</span> for <span class="math-container">$x$</span>,
so <span class="math-container">$\sum_{j\in S} x_j = \lambda$</span>.
Then the 1-to-<span class="math-container">$k$</span> matching <span class="math-container">$M$</span> defined by
<span class="math-container">$M(1) = S$</span> and <span class="math-container">$M(2) = [2n']\setminus S$</span>
has cost <span class="math-container">$\lambda$</span>.
Conversely, suppose that there is a 1-to-<span class="math-container">$k$</span> matching <span class="math-container">$M$</span>
of cost at most <span class="math-container">$\lambda$</span>.
Then taking <span class="math-container">$S=M(1)$</span> gives a feasible subset for <span class="math-container">$x$</span>. <span class="math-container">$~~~\Box$</span></p>
<hr />
<p><em>Proof of Lemma 2.</em> The proof is by reduction from the strongly NP-hard <a href="https://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow noreferrer">3-Partition</a> problem.
Fix an instance <span class="math-container">$x \in \mathbb N^{3n}$</span> of 3-Partition.
The goal is to determine whether there is a partition <span class="math-container">$C$</span> of <span class="math-container">$[3n]$</span>
into <span class="math-container">$n$</span> triples such that <span class="math-container">$\sum_{j\in C_i} x_j$</span> equals <span class="math-container">$\lambda$</span>
for each triple <span class="math-container">$C_i$</span> in <span class="math-container">$C$</span>,
where <span class="math-container">$\lambda = \sum_{j=1}^{3n} x_j/n$</span>.</p>
<p>Given <span class="math-container">$x$</span>, the reduction outputs the instance <span class="math-container">$(n, k, w, \lambda)$</span> of the decision version of OP's problem where
<span class="math-container">$k=3$</span>, and <span class="math-container">$w_{ij} = x_j$</span>
for <span class="math-container">$(i, j) \in [n]\times [3n]$</span>.</p>
<p>Next we verify that the reduction is correct.
Suppose that there is a feasible partition <span class="math-container">$C$</span> for <span class="math-container">$x$</span>,
so <span class="math-container">$\sum_{j\in C_i} x_j = \lambda$</span> for each triple <span class="math-container">$C_i$</span> in <span class="math-container">$C$</span>.
Then the 1-to-3 matching <span class="math-container">$M$</span> defined by
<span class="math-container">$M(i) = C_i$</span> for each <span class="math-container">$i\in [n]$</span>
has cost <span class="math-container">$\lambda$</span>.</p>
<p>Conversely, suppose that there is a 1-to-3 matching <span class="math-container">$M$</span>
of cost at most <span class="math-container">$\lambda$</span>.
Then taking <span class="math-container">$C_i=M(i)$</span> for <span class="math-container">$i\in [n]$</span> gives a feasible partition <span class="math-container">$C$</span> for <span class="math-container">$x$</span>. <span class="math-container">$~~~\Box$</span></p>
<hr />
<p><em>Proof of Lemma 3.</em>  For any instance with <span class="math-container">$n=1$</span>, there is only one possible solution <span class="math-container">$M(1) = [k]$</span>, so the optimum can be found in linear time.</p>
<p>Given an instance <span class="math-container">$(k=1, n, w, \lambda)$</span> of the decision variant of OP's problem, the instance can be solved by reduction to the bipartite matching instance <span class="math-container">$G=(U, W, E)$</span> where <span class="math-container">$U = W = [n]$</span> and <span class="math-container">$E = \{(i, j) : w_{ij} \le \lambda\}$</span>, which has a perfect matching iff OP's instance has a 1-to-1 matching of cost at most <span class="math-container">$\lambda$</span>.</p>
<p>The optimization version of OP's problem can be solved using <span class="math-container">$O(\log n)$</span> iterations of binary search, over <span class="math-container">$\lambda$</span> in <span class="math-container">$\{w_{ij} : (i, j) \in [n] \times [n]\}$</span>, to find the minimum <span class="math-container">$\lambda$</span> such that there is a solution of cost at most <span class="math-container">$\lambda$</span>.</p>
<p>EDIT: The case <span class="math-container">$k=1$</span> was asked about <a href="https://cstheory.stackexchange.com/questions/32321/weighted-matching-algorithm-for-minimizing-max-weight">here</a>.  (Answers pointed out that it is studied under the name Bottleneck Matching.)
<span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2024-04-14T16:32:09.300Z
2024-04-14T16:38:35.113Z
2024-04-14T16:38:35.113Z
Neal Young
<p>Similar with <a href="https://cstheory.stackexchange.com/questions/32321/weighted-matching-algorithm-for-minimizing-max-weight">Weighted matching algorithm for minimizing max weight</a>. Consider the following matching problem:</p>
<p>Input: a complete weighted bipartite graph with <span class="math-container">$n+(k*n)$</span> vertices, given by <span class="math-container">$n$</span>, <span class="math-container">$k*n$</span>, and <span class="math-container">$w_{ij}$</span> a weight matrix for each edge connecting <span class="math-container">$i \in [n]$</span> and <span class="math-container">$j \in [k*n]$</span>.</p>
<p>Output: a perfect &quot;1-to-k&quot; matching :<span class="math-container">$[]↣[k*n]^k$</span> where each vertices on the left side is equally connected to <span class="math-container">$k$</span> vertices on the right side, minimizing the following function:</p>
<p><span class="math-container">$max_i\Sigma_{j\in M(i)}w_{ij}$</span>.</p>
<p>Is this NP-hard problem or a polynomial way to solve it?</p>

CC BY-SA 4.0
2024-04-13T15:03:28.887Z
(i) I assume you intend that each vertex on the right should be matched to just *one* vertex on the left.  (ii) Per the posting guidelines, can you explain where the problem arises for you, and what you've tried?   (iii) Seems to me like it's in P by an easy reduction to matching.
Neal Young
CC BY-SA 4.0
2024-04-14T03:59:43.740Z
@NealYoung (i) Yes, every vertex on the right should be matched to only one vertex on the left. (ii) I'm building a distributed cache system with a cache on each worker, and the input data is batches of sets of elements (e.g., a batch of token sequence), I want to evenly allocate these samples to the most proper worker to maximize the cache hit and minimize extra communication overhead.
Han Tian
CC BY-SA 4.0
2024-04-14T16:33:32.947Z
I spoke too soon... the problem is NP-hard (even for fixed $n\ge 2$, or fixed $k\ge 3$).  The restrictions to $k=1$ or $n=1$ are in P.  I'm not sure about the restriction to $k=2$.
Neal Young
CC BY-SA 4.0
2024-04-14T16:40:10.983Z
Closely related:  https://cstheory.stackexchange.com/questions/54185/how-can-i-optimize-the-assignment-of-object-sets-to-workers-with-pre-existing-ca ?
Neal Young
<graph-algorithms><matching>
Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight
Han Tian
# Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

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

Similar with [Weighted matching algorithm for minimizing max weight](https://cstheory.stackexchange.com/questions/32321/weighted-matching-algorithm-for-minimizing-max-weight). Consider the following matching problem:

Input: a complete weighted bipartite graph with $n+(k\*n)$ vertices, given by $n$, $k\*n$, and $w\_{ij}$ a weight matrix for each edge connecting $i \in [n]$ and $j \in [k\*n]$.

Output: a perfect "1-to-k" matching :$[]↣[k\*n]^k$ where each vertices on the left side is equally connected to $k$ vertices on the right side, minimizing the following function:

$max\_i\Sigma\_{j\in M(i)}w\_{ij}$.

Is this NP-hard problem or a polynomial way to solve it?

**Tags:** graph-algorithms, matching

> **Comments:**
> **username_1**: (i) I assume you intend that each vertex on the right should be matched to just *one* vertex on the left.  (ii) Per the posting guidelines, can you explain where the problem arises for you, and what you've tried?   (iii) Seems to me like it's in P by an easy reduction to matching.  
> **username_0**: @NealYoung (i) Yes, every vertex on the right should be matched to only one vertex on the left. (ii) I'm building a distributed cache system with a cache on each worker, and the input data is batches of sets of elements (e.g., a batch of token sequence), I want to evenly allocate these samples to the most proper worker to maximize the cache hit and minimize extra communication overhead.  
> **username_1**: I spoke too soon... the problem is NP-hard (even for fixed $n\ge 2$, or fixed $k\ge 3$).  The restrictions to $k=1$ or $n=1$ are in P.  I'm not sure about the restriction to $k=2$.  
> **username_1**: Closely related:  https://cstheory.stackexchange.com/questions/54185/how-can-i-optimize-the-assignment-of-object-sets-to-workers-with-pre-existing-ca ?  

---

## 1 answers

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

The problem is hard if $k$ is part of the input (not fixed):

**Lemma 1.** *The problem is NP-hard, even for $n=2$.*

The problem is also hard if $k$ (but not $n$) is fixed (with $k\ge 3$):

**Lemma 2.** *The problem is strongly NP-hard, even for $k=3$.*

The problem is in P if $k=1$ or $n=1$:

**Lemma 3.** *The problem is in P for $k=1$ or $n=1$.*

**We leave open whether the problem is NP-hard for $k=2$.**

---

*Proof of Lemma 1.* The proof is by reduction from the NP-hard [Two-Way Balanced Partition](https://en.wikipedia.org/wiki/Balanced_number_partitioning#Two-way_balanced_partitioning) problem.
Fix an instance $x \in \mathbb N^{2n'}$ of Two-Way Balanced Partition.
The goal is to determine whether there is a subset $S\subseteq [2n']$
of size $n'$
such that $\sum\_{j\in S} x\_j = \lambda$,
where $\lambda = \sum\_{j=1}^{2n'} x\_j / 2$.
Given $x$, the reduction outputs the instance $(n, k, w, \lambda)$ of the decision version of OP's problem
$n=2$, $k=n'$, and $w\_{ij} = x\_j$
for $(i, j) \in [2]\times [2n']$.

Next we verify that the reduction is correct.
Suppose that there is a feasible subset $S$ for $x$,
so $\sum\_{j\in S} x\_j = \lambda$.
Then the 1-to-$k$ matching $M$ defined by
$M(1) = S$ and $M(2) = [2n']\setminus S$
has cost $\lambda$.
Conversely, suppose that there is a 1-to-$k$ matching $M$
of cost at most $\lambda$.
Then taking $S=M(1)$ gives a feasible subset for $x$. $~~~\Box$

---

*Proof of Lemma 2.* The proof is by reduction from the strongly NP-hard [3-Partition](https://en.wikipedia.org/wiki/3-partition_problem) problem.
Fix an instance $x \in \mathbb N^{3n}$ of 3-Partition.
The goal is to determine whether there is a partition $C$ of $[3n]$
into $n$ triples such that $\sum\_{j\in C\_i} x\_j$ equals $\lambda$
for each triple $C\_i$ in $C$,
where $\lambda = \sum\_{j=1}^{3n} x\_j/n$.

Given $x$, the reduction outputs the instance $(n, k, w, \lambda)$ of the decision version of OP's problem where
$k=3$, and $w\_{ij} = x\_j$
for $(i, j) \in [n]\times [3n]$.

Next we verify that the reduction is correct.
Suppose that there is a feasible partition $C$ for $x$,
so $\sum\_{j\in C\_i} x\_j = \lambda$ for each triple $C\_i$ in $C$.
Then the 1-to-3 matching $M$ defined by
$M(i) = C\_i$ for each $i\in [n]$
has cost $\lambda$.

Conversely, suppose that there is a 1-to-3 matching $M$
of cost at most $\lambda$.
Then taking $C\_i=M(i)$ for $i\in [n]$ gives a feasible partition $C$ for $x$. $~~~\Box$

---

*Proof of Lemma 3.* For any instance with $n=1$, there is only one possible solution $M(1) = [k]$, so the optimum can be found in linear time.

Given an instance $(k=1, n, w, \lambda)$ of the decision variant of OP's problem, the instance can be solved by reduction to the bipartite matching instance $G=(U, W, E)$ where $U = W = [n]$ and $E = \{(i, j) : w\_{ij} \le \lambda\}$, which has a perfect matching iff OP's instance has a 1-to-1 matching of cost at most $\lambda$.

The optimization version of OP's problem can be solved using $O(\log n)$ iterations of binary search, over $\lambda$ in $\{w\_{ij} : (i, j) \in [n] \times [n]\}$, to find the minimum $\lambda$ such that there is a solution of cost at most $\lambda$.

EDIT: The case $k=1$ was asked about [here](https://cstheory.stackexchange.com/questions/32321/weighted-matching-algorithm-for-minimizing-max-weight). (Answers pointed out that it is studied under the name Bottleneck Matching.)
$~~~~\Box$


---

