1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ NP-Hard on which parameter? $k$? $\endgroup$ Dec 27, 2023 at 1:19
  • $\begingroup$ @user3508551 yes. $\endgroup$
    – Michael C.
    Dec 27, 2023 at 4:35
  • $\begingroup$ @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. $\endgroup$
    – Michael C.
    Dec 27, 2023 at 13:51

1 Answer 1

1
$\begingroup$

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$

$\endgroup$

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.