# A variant of the generalised assignment problem

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

• NP-Hard on which parameter? $k$? Dec 27, 2023 at 1:19
• @user3508551 yes. Dec 27, 2023 at 4:35
• @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 cs.stackexchange.com, so I deleted the other. Dec 27, 2023 at 13:51

OP's problem generalizes the 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, Feige has shown that if there is such an algorithm with $$c < 1 - 1/e$$, then P=NP. $$~~~\Box$$