Name
Abstract | ||
|---|---|---|
This article deals with a bi-objective matching problem. The input is a complete graph and two values on each edge (a weight and a length) which satisfy the triangle inequality. It is unlikely that every instance admits a matching with maximum weight and maximum length at the same time. Therefore, we look for a compromise solution, i.e. a matching that simultaneously approximates the best weight and the best length. For which approximation ratio can we guarantee that any instance admits a -approximate matching? We propose a general method which relies on the existence of an approximate matching in any graph of small size. An algorithm for computing a 1/3-approximate matching in any instance is provided. The algorithm uses an analytical result stating that every instance on at most 6 nodes must admit a 1/2-approximate matching. We extend our analysis with a computer-aided approach for larger graphs, indicating that the general method may produce a 2/5-approximate matching. We conjecture that a 1/2-approximate matching exists in any bi-objective instance satisfying the triangle inequality. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.01.012 | Theor. Comput. Sci. |
Keywords | Field | DocType |
Bi-objective optimization,Approximation algorithm,Matching | Approximation algorithm,Complete graph,Graph,Discrete mathematics,Combinatorics,Optimal matching,Approximate matching,Triangle inequality,3-dimensional matching,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
670 | C | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Gourvès | 1 | 241 | 30.97 |
| Jérôme Monnot | 2 | 512 | 55.74 |
| Fanny Pascual | 3 | 97 | 14.48 |
| Daniel Vanderpooten | 4 | 1153 | 74.66 |