0
$\begingroup$

The following is small-scale example is meant to illustrate the general distribution problem

Consider 4 parks, each with exactly 1 pond. Parks are marked as vertices in the following undirected graph:

desc

Each park has a number of ducks in them, and each pond has a maximum capacity of ducks (the parks themselves do not have a max capacity):

  • Park A has 8 ducks and its pond has a max capacity of 5 ducks.
  • Park B has 4 ducks and its pond has a max capacity of 6 ducks.
  • Park C has 10 ducks and its pond has a max capacity of 4 ducks.
  • Park D has 11 ducks and its pond has a max capacity of 9 ducks.

Now, all ducks have to fly to a pond in another park. Ducks can only fly to adjacent parks as marked by the edges - or they can fly away if all adjacent ponds are full (meaning that surplus/leftover ducks are not important wrt. the objective and can be ignored). The objective is to fill all ponds to their max capacity.

Is there an algorithm or a class of algorithms that can be used for this problem? I am not interested in the solution for the example, but rather more general approaches (though you are of course welcome to use the example to demonstrate a general approach).

Cheers!

$\endgroup$
1
  • $\begingroup$ Could you clarify what you mean by "they can fly away if all adjacent ponds are full"? $\endgroup$ Sep 1, 2023 at 14:38

1 Answer 1

2
$\begingroup$

This can be solved with max-flow: create a bipartite graph with parks on one side and ponds on another, have an edge with infinite capacity if a duck from park A can fly to pond B, and for each park have an edge from the source to it whose capacity is the number of ducks at that park, and for each pond an edge to the sink with the pond's capacity.

$\endgroup$
0

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.