LP-relaxed matching with zero-cost loops
(English)Manuscript (preprint) (Other academic)
We study a certain LP-relaxation of the minimum matching problem on a complete graph with random edge costs. In earlier work by Wästlund it was shown that the expected cost of the optimum solution has the simple form 1 – 1/4 + 1/9 – ··· ± 1/n2, an analogue of a corresponding formula for the bipartite problem. Wegeneralize by conditioning on certain edges having zero cost. It is proved that if each node independently is given a zero-cost loop with probability 1 ¡ p then the expected cost of the optimum solution is p – p2/4 + p3/9 – ··· ± pn/n2.
IdentifiersURN: urn:nbn:se:liu:diva-51716OAI: oai:DiVA.org:liu-51716DiVA: diva2:277090