Theoretical Computer Science Asked by Karagounis Z on October 30, 2021
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The only part I don’t understand is on page 4-5, when they claim that $tilde x(tilde delta(U)) geq tilde x(tilde delta(X’ setminus W’)) + tilde x(tilde delta(W setminus X))$. I don’t understand why this doesn’t hold with equality, since the values on copied edges in the duplicated graph are identical.
Can someone clarify this proof? Is it a mistake?
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP