LP-relaxed matching with zero-cost loops

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

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Keyword

MATHEMATICS

MATEMATIK

Publication and Content Type

vet (subject category)

ovr (subject category)