Symmetric traveling salesman problem and flows in hypergraphs: New algorithmic possibilities
| Autor: | Tiru S. Arthanari |
|---|---|
| Jazyk: | English<br />Italian |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali, Vol 97, Iss 1, p A1 (2019) |
| Druh dokumentu: | article |
| ISSN: | 0365-0359 1825-1242 |
| DOI: | 10.1478/AAPP.971A1 |
| Popis: | The traveling salesperson problem (TSP) is a very well-known NP-hard combinatorial optimization problem. Many different integer programming formulations are known for the TSP. Some of them are "compact"", in the sense of having a polynomially-bounded number of variables and constraints. We focus on one compact formulation for the symmetric TSP, known as the "multistage insertion" formulation [T. S. Arthanari, Discrete Mathematics 306, 1474 (2006)], and show that its linear programming (LP) relaxation can be viewed as a minimum-cost flow problem in a hypergraph. Using some ideas of R. Cambini, G. Gallo and M. G. Scutella' [University of Pisa, TR-1/92 (1992)] on flows in hypergraphs, we propose new algorithms to solve the LP relaxation. We also exploit the Leontief structure of a certain subproblem, to provide additional algorithms for solving the LP relaxation. Some bounds on the running time are also derived. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|