EUVIMEDObjevte EUVIMED
Crossref

Revisiting a Cutting-Plane Method for Perfect Matchings

Amber Q. Chen, Kevin K. H. Cheung, P. Michael Kielstra, Avery D. Winn

Open Journal of Mathematical Optimization · 2020

DOI: 10.5802/ojmo.2 ↗

At a glance

Journal article in Open Journal of Mathematical Optimization, 2020. Written by Amber Q. Chen and 3 co-authors. Cited 1 times so far (Crossref); 16 references.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

In 2016, Chandrasekaran, Végh, and Vempala ( Mathematics of Operations Research , 41(1):23–48) published a method to solve the minimum-cost perfect matching problem on an arbitrary graph by solving a strictly polynomial number of linear programs. However, their method requires a strong uniqueness condition, which they imposed by using perturbations of the form c ( i ) = c 0 ( i ) + 2 - i . On large graphs (roughly m > 100 ), these perturbations lead to cost values that exceed the precision of floating-point formats used by typical linear programming solvers for numerical calculations. We demonstrate, by a sequence of counterexamples, that perturbations are required for the algorithm to work, motivating our formulation of a general method that arrives at the same solution to the problem as Chandrasekaran et al . but overcomes the limitations described above by solving multiple linear programs without using perturbations. The key ingredient of our method is an adaptation of an algorithm for lexicographic linear goal programming due to Ignizio ( Journal of the Operational Research Society , 36(6):507–515, 1985). We then give an explicit algorithm that exploits our method, and show that this new algorithm still runs in strongly polynomial time.

Cite

APA

Chen, A. Q., Cheung, K. K. H., Kielstra, P. M., & Winn, A. D. (2020). Revisiting a Cutting-Plane Method for Perfect Matchings. Open Journal of Mathematical Optimization. https://doi.org/10.5802/ojmo.2

Vancouver

Chen AQ, Cheung KKH, Kielstra PM, Winn AD. Revisiting a Cutting-Plane Method for Perfect Matchings. Open Journal of Mathematical Optimization. 2020. doi:10.5802/ojmo.2

BibTeX
@article{Chen2020,
  author = {Chen, Amber Q. and Cheung, Kevin K. H. and Kielstra, P. Michael and Winn, Avery D.},
  title = {Revisiting a Cutting-Plane Method for Perfect Matchings},
  journal = {Open Journal of Mathematical Optimization},
  year = {2020},
  doi = {10.5802/ojmo.2}
}
Start for free →