I have been looking for a proof of the following statement. I think it follows from the proof of the integrality of the matching polytope but I am not so sure.

Given a bipartite graph $G=(A \cup B, E)$ with edge weights $w: E \mapsto R_+$, define a fractional incomplete assignment as $x: E \mapsto [0,1]$ such that for each vertex $v \in A$, $1/2 \le \sum_{u: (u,v) \in E} x((u,v)) \le 1$, define the cost of the assignment to be $\sum_{(u,v) \in E} x((u,v))\cdot w((u,v))$.

Statement: For any fractional incomplete assignment $x$, there exists a mapping $y : E \mapsto \{0,1\}$ such that for all $v \in A$, $\sum_{u: (u,v) \in E} y((u,v)) \le 1$ and $\sum_{(u,v) \in E} y((u,v)) = \lfloor \sum_{(u,v) \in E} x((u,v))\rfloor$ and the cost of $y$ is at most the cost of $x$ (I would be happy with constant factor higher here but I don't see why it should be the case).

I apologie in advance if this sounds super trivial but I somehow cannot find a simple proof.

Note: in the case of $x$ satisfying in addition: for each vertex $v \in A$, $\sum_{u: (u,v) \in E} x((u,v)) = 1$, it is the assignment problem (or bipartite perfect matching) and the statement is well known.


Your Answer

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

Browse other questions tagged or ask your own question.