3
$\begingroup$

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.

$\endgroup$

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.