Best approach to resource allocation problem

Question

Problem

The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city than the enemy, we retake the city. Our aim is to distribute our teams so that we maximise the number of retaken cities if:

1. We can only place one team per city
2. There is no limit to the number of teams we can play in each city.

Question

I'm trying to figure out which approach might be best for each option (greedy algorithm, divide-and-conquer, dynamic programming, backtracking). I'm not necessarily looking for the particular algorithm, although I'd be happy to get it too.

Previous work

One team per city

The best approach would be a greedy algorithm, which would assign to each city the smallest team which can defend it, starting from the smallest team. If at some point the smallest remaining team cannot take the smallest remaining city, we can simply dump that team.

No restriction for the number of teams per city

I can think of a greedy algorithm similar to the previous one, in which we assign the smallest teams to the smallest city until it's defended, and then move to the next one. However, I am not certain this would lead to an optimal solution, unlike the previous case. Backtracking explores the solution space exhaustively, so it would work but it's ineffective. Dynamic programming looks promising, as this superficially looks like a variation of the knapsack problem, but I know that generalisations/variations might not necessarily be tackled with the same approach.

Answer 1

The second variant of your problem can be also stated as a Bin covering problem and vice-versa. Let us see how.

You can assume $n$ bins of capacities: $(e_{1}+1)$, $\dotsc$, $(e_{n-1}+1)$ and $(e_{n}+1)$. And, $n$ items of sizes: $d_{1}$, $\dotsc$, $d_{n-1}$ and $d_{n}$. The bin covering problem asks you to maximize the number of bins filled such that the total size of items packed in a bin is at least the capacity of that bin. Therefore, this problem is equivalent to the second variant of your problem. You can carry out a similar reduction in the reverse direction also, which proves that both the problems are equivalent.

---

Since the Bin covering problem is known to be strongly $\mathsf{NP}$-hard (see Section 2 on page 7 of this research paper.), it implies that the second variant of your problem is also strongly $\mathsf{NP}$-hard. Therefore, there is no polynomial or pseudo-polynomial time algorithm for your problem assuming $\mathsf{P} \neq \mathsf{NP}$. This closes the open problem posed by Watercrystal.

Answer 2

Let us first show that your proposed greedy algorithm for the second restriction is not optimal. For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $d_3 = 3$. The greedy algorithm would assign $d_1$ and $d_2$ to the first city and $d_3$ to the second one, leading to only one city being retaken. However, if we assign $d_2$ to the first city and $d_1$ and $d_3$ to the second one we could retake both of them and hence, the greedy algorithm is not optimal.

As for algorithmic approaches, note that your problem given the second restriction (let's denote it by $L$) is $\mathsf{NP}$-complete which can be shown by reducing $\mathrm{Partition}$ to $L$: For a $\mathrm{Partition}$ instance given by a multiset $S$ of integers define an $L$-instance where the multiset of the $d_i$s is given by $S$, i.e. for every element of $S$ we create a team of the same size. Denote by $X$ the sum of the elements of $S$ and set $e_1 = e_2 = X/2 - 1$ as well as $e_i = X + 1$ for all $i > 2$. Now note that we can retake at most $2$ cities (as we don't have enough forces to retake any city which is held by at least $X$ soldiers) and we can only retake both of them if we can split our forces exactly in half, sending $X/2$ soldiers to the first and second city, respectively. It follows that $S$ is a yes-instance of $\mathrm{Partition}$ if and only if we can retake 2 cities in our constructed $L$-instance (I left out some technical details but this reduction should work out just fine).

Assuming $\mathsf{P} \neq \mathsf{NP}$ this result implies that $L$ has no (deterministic) polynomial time algorithm. For some further lower bounds, see the other answer.