Search: onr:"swepub:oai:DiVA.org:liu-51716" >
LP-relaxed matching...
Abstract
Subject headings
Close
- 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)
To the university's database