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.

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

MATHEMATICS

MATEMATIK

Publikations- och innehållstyp

vet (ämneskategori)

ovr (ämneskategori)