Revisiting a Cutting-Plane Method for Perfect Matchings
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 cond...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2020-12-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.2/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204953095864320 |
|---|---|
| author | Chen, Amber Q. Cheung, Kevin K. H. Kielstra, P. Michael Winn, Avery D. |
| author_facet | Chen, Amber Q. Cheung, Kevin K. H. Kielstra, P. Michael Winn, Avery D. |
| author_sort | Chen, Amber Q. |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3b5c40279444489380da21667fc301ce |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2020-12-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-3b5c40279444489380da21667fc301ce2025-02-07T14:02:14ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602020-12-01111510.5802/ojmo.210.5802/ojmo.2Revisiting a Cutting-Plane Method for Perfect MatchingsChen, Amber Q.0Cheung, Kevin K. H.1Kielstra, P. Michael2Winn, Avery D.3University of Waterloo, 200 University Ave. W., Waterloo, ON N2L 3G1, CanadaCarleton University, 1125 Colonel By Dr., Ottawa, ON K1S 5B6, CanadaHarvard University, 1 Oxford Street, Cambridge, MA 02138, USAUniversity of Michigan, 530 S State St., Ann Arbor, MI 48109, USAIn 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.2/perfect matchinguniquenessperturbationlexicographic linear goal programmingcutting-plane |
| spellingShingle | Chen, Amber Q. Cheung, Kevin K. H. Kielstra, P. Michael Winn, Avery D. Revisiting a Cutting-Plane Method for Perfect Matchings Open Journal of Mathematical Optimization perfect matching uniqueness perturbation lexicographic linear goal programming cutting-plane |
| title | Revisiting a Cutting-Plane Method for Perfect Matchings |
| title_full | Revisiting a Cutting-Plane Method for Perfect Matchings |
| title_fullStr | Revisiting a Cutting-Plane Method for Perfect Matchings |
| title_full_unstemmed | Revisiting a Cutting-Plane Method for Perfect Matchings |
| title_short | Revisiting a Cutting-Plane Method for Perfect Matchings |
| title_sort | revisiting a cutting plane method for perfect matchings |
| topic | perfect matching uniqueness perturbation lexicographic linear goal programming cutting-plane |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.2/ |
| work_keys_str_mv | AT chenamberq revisitingacuttingplanemethodforperfectmatchings AT cheungkevinkh revisitingacuttingplanemethodforperfectmatchings AT kielstrapmichael revisitingacuttingplanemethodforperfectmatchings AT winnaveryd revisitingacuttingplanemethodforperfectmatchings |