5
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Have you considered the possibility that this problem is hard? $\endgroup$ – Yuval Filmus May 24 '18 at 16:28
  • $\begingroup$ The thought had occurred to me, but I haven't been able to think of an NP-complete problem that can be reduced to this one. $\endgroup$ – M42 May 24 '18 at 17:24
  • $\begingroup$ Suppose $x= y$ and I ask you "can you fit all the apples and leaves all the boxes half full"? Then this problem asks for a perfect matching. So if you have an algorithm, it solves the matching problem in particular - which is polytime but not exactly trivial. Actually, I believe your problem can be reduced to a matching problem. Have you considered it? $\endgroup$ – Manuel Lafond May 25 '18 at 4:08
  • $\begingroup$ Oh, interesting. Yes, I think you can formulate the problem as a maximum matching problem for a bipartite graph -- have a vertex for each apple and each box, and add an edge between an apple and a box iff the apple can be placed into the box. Then I think the greatest number of half full boxes is the size of the maximum matching. The only problem is that the maximum matching might have left some apples unmatched, and now I need to figure out how to place these remaining apples. $\endgroup$ – M42 May 25 '18 at 17:30
  • $\begingroup$ Yes, it's not exactly a matching because some boxes might be matched with more than one apple. One trick you can use is to have 3 vertices per box, so that they form a triangle. Then assign a weight on each edge of the triangle. Then after you match the apples, each half-full box can use an edge of the triangle, so that a maximum weight matching will maximize half-full boxes. Anyway, I don't know if it's clear to you, but you should try, and if it doesn't work I can make a full answer. $\endgroup$ – Manuel Lafond May 25 '18 at 19:03
2
$\begingroup$

Here is the reduction to a maximum matching, following the comments. We construct a graph $G$ with weighted edges as follows. The vertices of $G$ are $A$ and $B$.

Each apple has a corresponding vertex $a$ in $A$, and each box $b$ has $3$ corresponding vertices $b_1,b_2,b_3$ in $B$. Add the edges $b_1b_2, b_2b_3$ and $b_1b_3$ so that they form a triangle, and put a weight of $1$ to each of these $3$ edges.

Now, for each apple $a$ that is allowed to go into box $b$, add the edges $ab_1, ab_2$ and $ab_3$, each with a high weight, say $n^2$ (where here $n = x + y$).

Now consider any maximum weight matching $M$. Then $M$ must place as many apples in boxes as possible, due to the high weight of the edges incident to the $A$ vertices. Also, $M$ must maximize the number of half-full boxes while doing so. This is because if a box $b$ is half-full, then at least two of its vertices are unmatched with apples, so the edge of weight $1$ can be added into the matching. However, if a box is not half-full, no edge of the $b_1b_2b_3$ triangle can be added into the matching. In other words, each half-full box allows us to add a weight $1$ edge into $M$.

Improve this answer
$\endgroup$
  • $\begingroup$ And finding the maximum weight matching for a general graph can be done in polynomial time with the blossom algorithm (en.wikipedia.org/wiki/Blossom_algorithm). Thanks! $\endgroup$ – M42 May 29 '18 at 18:21
2
$\begingroup$

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:

  1. Make a node for each apple and construct an edge from the source $s$ with capacity $[1, 1]$.

  2. 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]$.

  3. Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $[0, 1]$.

  4. Connect each box's output node to the sink $t$ with capacity $[0, 1]$.

  5. 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.

Improve this answer
$\endgroup$
  • $\begingroup$ And to make this a bit faster you can use binary search on $n$ to find the smallest $n$ where this has a feasible solution. $\endgroup$ – D.W.♦ May 26 '18 at 3:41
  • $\begingroup$ @D.W. If we use a $O(V^3)$ max flow algorithm then the total complexity becomes $O((x+y)^3 \log(y))$, which seems quite reasonable. For what it's worth, we don't actually need max flow - merely feasible integer flow. Do you know of an asymptotically faster algorithm than $O(V^3)$ for just feasible integer flow? $\endgroup$ – orlp May 26 '18 at 11:40
  • $\begingroup$ Yeah. I don't know of anything faster. $\endgroup$ – D.W.♦ May 26 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.