All Questions
Tagged with perfect-matchings combinatorial-optimization
5 questions
1
vote
0
answers
17
views
Complexity of optimal cartesian matching
Question:
what is known about the algorithmic aspects of optimally matching a set $\mathcal{P} = \prod\limits_{i=1}^n \left(1,\,\cdots,\,k_i\right)$ of grid-points to a set of $\prod\limits_{i=1}^...
- 13.2k
1
vote
1
answer
104
views
Symmetry of optimal solutions to symmetric assignment problems
Is there a sound proof of or a counter example to the following conjecture:
if $\boldsymbol{A}^T=\boldsymbol{A}$ is the cost-matrix of a bipartite assignment problem with unique optimal assignment,
...
- 13.2k
4
votes
2
answers
318
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
-2
votes
1
answer
174
views
What is known about iterated matching as a TSP heuristic
A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...
- 13.2k
5
votes
1
answer
316
views
On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights
Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...
- 4,878