I am working with a set L of land parcels and a set C of counties. Each parcel L_i costs m dollars and takes up b acres. Each county C_i requires n acres of parcels. Assume for now that the counties do not care about getting a bit more than n acres if the last parcel to be allocated to them "overfills" their capacity. Finally, L_i must be within x miles of the C_i's centroid to be considered for allocation to C_i.

I designed an allocation algorithm to solve this problem such that C_i achieves n acres while minimizing cost m. However, the design is incredibly computationally intensive. Let L_c be the land parcels within x miles of C_i. My algorithm sorts L_c by cost in ascending order, allocates the first n-acres, then moves on to the next county.

Any ideas on how to make this more efficient? Are there established algorithms designed for such allocation problems?

CodePudding user response：

This problem is extraordinarily difficult. Even without the "distance to centroid" restriction, the problem reduces to SUBSET-SUM which is NP-Complete (and adding the distance restriction does not change this). The short, informal proof is that if you wanted to solve an instance of SUBSET-SUM with some solution to this problem as an oracle, you could make it such that C_1 wants the target subset sum and C_2 wants the rest. That is to say, you won't find an efficient algorithm for solving this problem with perfect accuracy. That being said, you can get a pretty good algorithm that's pretty fast, sacrificing the accuracy of the solution to drastically speed it up.

The solution idea would be similar to yours, except you can use some BST to find unchosen parcels of land that are of maximal size but still don't overflow the C_i limit, until no additional parcel overfills C_i. Then, simply replace one of your chosen parcels with a slightly larger one such that you meet or exceed your quota (or just take another one, if it's easier). This will leave as many parcels of land available for other cities while still meeting C_i's quota. Then, continue to the next city.

You might be able to try and solve a better approximation for this with some form of integer simplex, but I wouldn't recommend going down that route. Sorry to give you the bad news, but you won't be finding any satisfyingly efficient algorithm that is 100% accurate anytime soon :(