Name
Abstract | ||
|---|---|---|
Let P be a set of 3k points in the Euclidean plane. A 3-matching is a partition of P into k subsets of 3 points each, called triplets. The cost of each triplet {a, b, c} is given by min{|ab| + |bc|, |bc| + |ca|, |ca| + |ab|}, and the cost of the 3-matching is the sum of the costs of its triplets. The problem of finding a minimum cost Euclidean 3-matching is known to be NP-hard. Two integer programming formulations for this problem were introduced by Johnsson, Magyar, and Nevalainen. First, we prove that the linear programming relaxations of these two models are equivalent. Second, we introduce a new triplet integer programming model. Third, we compare the linear programming relaxations of these three models. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/ICEEE.2015.7357953 | 2015 12th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE) |
Keywords | Field | DocType |
Euclidean 3-Matching Problem,Integer Programming,Linear Relaxation | Linear-fractional programming,Discrete mathematics,Mathematical optimization,Combinatorics,Change-making problem,Euclidean distance,Branch and cut,Branch and price,Integer programming,Cutting stock problem,Linear programming relaxation,Mathematics | Conference |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gualberto Vazquez Casas | 1 | 0 | 0.34 |
| Rodrigo Alexander Castro Campos | 2 | 0 | 1.35 |
| Marco A. Heredia | 3 | 0 | 0.34 |
| Francisco Javier Zaragoza Martínez | 4 | 5 | 3.91 |