<p>OP's problem generalizes the <a href="https://en.wikipedia.org/wiki/Maximum_coverage_problem" rel="nofollow noreferrer">maximum coverage problem</a>, a well-studied problem for which the best poly-time approximation ratio possibly is <span class="math-container">$1-1/e$</span>, unless P=NP.  So achieving a better ratio for OP's problem would imply P=NP.</p>
<p><strong>Lemma 1.</strong> <em>If OP's problem admits an approximation ratio better than <span class="math-container">$1-1/e$</span>, then P=NP.</em></p>
<p><em>Proof.</em> Given a collection <span class="math-container">$S$</span> of sets and an integer <span class="math-container">$k$</span>, the maximum-coverage problem is to choose a collection <span class="math-container">$C$</span> of <span class="math-container">$k$</span> of the given sets so as to maximize the size of the union of the chosen sets.</p>
<p>This reduces to OP's problem by taking each set in <span class="math-container">$S$</span> to be a worker and each element <span class="math-container">$i$</span> to be a task, and letting the profit of assigning a task <span class="math-container">$i$</span> to a worker <span class="math-container">$S$</span> to be <span class="math-container">$1$</span> if <span class="math-container">$i\in S$</span> and zero otherwise.  Then the profit of a given collection of sets equals the size of the union.  This gives an approximation-preserving reduction from maximum coverage to OP's problem.</p>
<p>So any poly-time <span class="math-container">$c$</span>-approximation algorithm for OP's problem would also be a poly-time <span class="math-container">$c$</span>-approximation algorithm for maximum coverage.  As observed in the <a href="https://en.wikipedia.org/wiki/Maximum_coverage_problem" rel="nofollow noreferrer">Wikipedia entry for maximum coverage</a>, Feige <a href="https://doi.org/10.1145%2F285055.285059" rel="nofollow noreferrer">has shown</a> that if there is such an algorithm with <span class="math-container">$c &lt; 1 - 1/e$</span>, then P=NP. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2023-12-28T22:27:20.007Z
2023-12-29T00:02:55.467Z
2023-12-29T00:02:55.467Z
Neal Young
<p>I am trying to solve this problem:</p>
<ol>
<li>There are <span class="math-container">$N$</span> workers and <span class="math-container">$T$</span> tasks.</li>
<li>Each task can be assigned to at most one worker.</li>
<li>Each worker can be assigned any number of tasks.</li>
<li>The profit obtained by assigning worker <span class="math-container">$i$</span> to task <span class="math-container">$j$</span> is <span class="math-container">$P_{ij}\geq 0$</span>.</li>
<li>At most <span class="math-container">$k$</span> out of the <span class="math-container">$N$</span> workers can be chosen to complete the <span class="math-container">$T$</span> tasks, where <span class="math-container">$1\leq k\leq N$</span>.</li>
</ol>
<p>The problem is a special case of the one discussed <a href="https://cstheory.stackexchange.com/questions/53030/generalized-assignment-problem-with-overall-budget">here</a>. Here the budget is <span class="math-container">$k$</span> and cost of every worker is 1.</p>
<p>What I have tried: Let <span class="math-container">$S\subseteq [N]$</span> be the set of chosen workers such that <span class="math-container">$|S|\leq k$</span>. For every task <span class="math-container">$t\in[T]$</span>, to maximise profit, assign it to the worker in <span class="math-container">$S$</span> who can bring in the maximum profit. So, the problem becomes:</p>
<p><span class="math-container">$$\max_{S\subseteq[N]:|S|\leq k}\sum_{t=1}^T\max_{j\in S}P_{jt}$$</span>.</p>
<p>The objective function becomes an instance of monotone, submodular set function maximization with cardinality constraints, so greedy algorithm yields a <span class="math-container">$1-e^{-1}$</span>-approximation. I also have a simple counter example to show that greedy algorithm need not give the optimal solution for some instances.</p>
<p>Is this problem NP-hard? I have an intuition it might be, but I am not able to prove it yet. If it is NP-hard, does it admit a better approximation ratio than <span class="math-container">$1-e^{-1}$</span>? Any hints or references would be really helpful. Thanks in advance.</p>

CC BY-SA 4.0
2023-12-27T01:19:03.433Z
NP-Hard on which parameter? $k$?
user3508551
CC BY-SA 4.0
2023-12-27T04:35:17.300Z
@user3508551 yes.
Michael C.
CC BY-SA 4.0
2023-12-27T13:51:14.577Z
@D.W. Sorry, I was not sure which SE was more suited for the question. I asked the question there and as I could not get an answer, I posted it here. Anyways, this version contains more information than the one in https://cs.stackexchange.com, so I deleted the other.
Michael C.
<reference-request><approximation-algorithms><approximation-hardness><submodularity>
A variant of the generalised assignment problem
Michael C.
# A variant of the generalised assignment problem

(Asked by: username_0 on 2023-12-26)

I am trying to solve this problem:

1. There are $N$ workers and $T$ tasks.
2. Each task can be assigned to at most one worker.
3. Each worker can be assigned any number of tasks.
4. The profit obtained by assigning worker $i$ to task $j$ is $P\_{ij}\geq 0$.
5. At most $k$ out of the $N$ workers can be chosen to complete the $T$ tasks, where $1\leq k\leq N$.

The problem is a special case of the one discussed [here](https://cstheory.stackexchange.com/questions/53030/generalized-assignment-problem-with-overall-budget). Here the budget is $k$ and cost of every worker is 1.

What I have tried: Let $S\subseteq [N]$ be the set of chosen workers such that $|S|\leq k$. For every task $t\in[T]$, to maximise profit, assign it to the worker in $S$ who can bring in the maximum profit. So, the problem becomes:

$$\max\_{S\subseteq[N]:|S|\leq k}\sum\_{t=1}^T\max\_{j\in S}P\_{jt}$$.

The objective function becomes an instance of monotone, submodular set function maximization with cardinality constraints, so greedy algorithm yields a $1-e^{-1}$-approximation. I also have a simple counter example to show that greedy algorithm need not give the optimal solution for some instances.

Is this problem NP-hard? I have an intuition it might be, but I am not able to prove it yet. If it is NP-hard, does it admit a better approximation ratio than $1-e^{-1}$? Any hints or references would be really helpful. Thanks in advance.

**Tags:** reference-request, approximation-algorithms, approximation-hardness, submodularity
> **Comments:**
> **username_1**: NP-Hard on which parameter? $k$?  
> **username_0**: @user3508551 yes.  
> **username_0**: @D.W. Sorry, I was not sure which SE was more suited for the question. I asked the question there and as I could not get an answer, I posted it here. Anyways, this version contains more information than the one in https://cs.stackexchange.com, so I deleted the other.  

---

## 1 answers

### Answer by username_2 on 2023-12-28. Score: 1 | Accepted answer

OP's problem generalizes the [maximum coverage problem](https://en.wikipedia.org/wiki/Maximum_coverage_problem), a well-studied problem for which the best poly-time approximation ratio possibly is $1-1/e$, unless P=NP. So achieving a better ratio for OP's problem would imply P=NP.

**Lemma 1.** *If OP's problem admits an approximation ratio better than $1-1/e$, then P=NP.*

*Proof.* Given a collection $S$ of sets and an integer $k$, the maximum-coverage problem is to choose a collection $C$ of $k$ of the given sets so as to maximize the size of the union of the chosen sets.

This reduces to OP's problem by taking each set in $S$ to be a worker and each element $i$ to be a task, and letting the profit of assigning a task $i$ to a worker $S$ to be $1$ if $i\in S$ and zero otherwise. Then the profit of a given collection of sets equals the size of the union. This gives an approximation-preserving reduction from maximum coverage to OP's problem.

So any poly-time $c$-approximation algorithm for OP's problem would also be a poly-time $c$-approximation algorithm for maximum coverage. As observed in the [Wikipedia entry for maximum coverage](https://en.wikipedia.org/wiki/Maximum_coverage_problem), Feige [has shown](https://doi.org/10.1145%2F285055.285059) that if there is such an algorithm with $c < 1 - 1/e$, then P=NP. $~~~\Box$


---

