Maintaining Perfect Matchings at Low Cost

Jannik Matuschke, Ulrike Schmidt-Kraepelin, José Verschae

The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, addi…