patternMinor
Algorithm to place apples in boxes
Viewed 0 times
algorithmplaceboxesapples
Problem
Suppose we have $x$ apples and $y$ boxes. Each box can fit at most 3 apples, and we say that a box is half full iff the box contains $\leq$ 1 apple. If each apple has a (non-empty) list of boxes that it can be placed in, what is a polynomial time algorithm that places apples in boxes such that the number of half full containers is maximized?
My attempt
Sort apples in ascending order of the number of boxes that they can be placed into. For each apple, if there is an empty box that it can be placed into, then place the apple there. Otherwise, if there is a box with 2 apples in it that the current apple can be placed into, place the apple in that box. Otherwise, place the apple in a half full box. This algorithm clearly runs in polynomial time, but I don't think it is optimal, especially since I haven't specified how to break ties between boxes.
My attempt
Sort apples in ascending order of the number of boxes that they can be placed into. For each apple, if there is an empty box that it can be placed into, then place the apple there. Otherwise, if there is a box with 2 apples in it that the current apple can be placed into, place the apple in that box. Otherwise, place the apple in a half full box. This algorithm clearly runs in polynomial time, but I don't think it is optimal, especially since I haven't specified how to break ties between boxes.
Solution
The below isn't necessarily a very practical algorithm, but (if I didn't make any mistakes) it shows this problem is in fact polynomial time.
I believe you can pose your problem as a series of integral maximum flow problems. I will phrase the problem with lower bound edge demands. This is equivalent to a regular flow problem.
We construct a maximum flow problem as follows:
-
Make a node for each apple and construct an edge from the source $s$ with capacity $[1, 1]$.
-
Made two nodes for each box (one input and one output node). For each apple that can fit in that box construct an edge from that apple to that box's input node with capacity $[0, 1]$. Connect the input and output node of each box with capacity $[0, 3]$.
-
Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $[0, 1]$.
-
Connect each box's output node to the sink $t$ with capacity $[0, 1]$.
-
Connect $A$ and $B$ to $t$ with respective capacities $[0, n]$ and $[0, n]$.
Now we will minimize the number of overfull boxes ($\geq 2$ apples), which is the same as maximizing the number of half full boxes. The critical observation is that each box can lose at most one of its apples to the sink - if it is overfull it must start flowing its apples through either $A$ or $B$. In the case of 3 apples both $A$ and $B$ must be utilized to maintain the $\text{out} - \text{in} = 0$ property of the flow problem.
Now when there is a feasible solution for $n = 0$ you know that there are no overfull boxes. Vice versa, if there exists a solution where there are no overfull boxes, there will be a feasible solution for $n = 0$.
Similarly, if there exists a solution where there are $k$ overfull boxes, there will be a feasible solution for $k = n$. This means that if we try all $n$ in increasing order, the first time we find a feasible solution we know it's optimal in $k$.
By inspecting the flow graph you can then find which apple goes in which box.
Since solving this maximum flow problem is polynomial in $x, y$ and $n$ is bounded in $y$, this algorithm is polynomial in the worst case as well.
I believe you can pose your problem as a series of integral maximum flow problems. I will phrase the problem with lower bound edge demands. This is equivalent to a regular flow problem.
We construct a maximum flow problem as follows:
-
Make a node for each apple and construct an edge from the source $s$ with capacity $[1, 1]$.
-
Made two nodes for each box (one input and one output node). For each apple that can fit in that box construct an edge from that apple to that box's input node with capacity $[0, 1]$. Connect the input and output node of each box with capacity $[0, 3]$.
-
Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $[0, 1]$.
-
Connect each box's output node to the sink $t$ with capacity $[0, 1]$.
-
Connect $A$ and $B$ to $t$ with respective capacities $[0, n]$ and $[0, n]$.
Now we will minimize the number of overfull boxes ($\geq 2$ apples), which is the same as maximizing the number of half full boxes. The critical observation is that each box can lose at most one of its apples to the sink - if it is overfull it must start flowing its apples through either $A$ or $B$. In the case of 3 apples both $A$ and $B$ must be utilized to maintain the $\text{out} - \text{in} = 0$ property of the flow problem.
Now when there is a feasible solution for $n = 0$ you know that there are no overfull boxes. Vice versa, if there exists a solution where there are no overfull boxes, there will be a feasible solution for $n = 0$.
Similarly, if there exists a solution where there are $k$ overfull boxes, there will be a feasible solution for $k = n$. This means that if we try all $n$ in increasing order, the first time we find a feasible solution we know it's optimal in $k$.
By inspecting the flow graph you can then find which apple goes in which box.
Since solving this maximum flow problem is polynomial in $x, y$ and $n$ is bounded in $y$, this algorithm is polynomial in the worst case as well.
Context
StackExchange Computer Science Q#92272, answer score: 2
Revisions (0)
No revisions yet.