| Article ID: | iaor20043359 |
| Country: | Belarus |
| Volume: | 47 |
| Issue: | 1 |
| Start Page Number: | 36 |
| End Page Number: | 40 |
| Publication Date: | Jan 2003 |
| Journal: | Doklady of the National Academy of Sciences of Belarus |
| Authors: | Proth Jean-Marie, Gordon V.S., Demidenko V.M. |
| Keywords: | optimization |
A system of linear inequalities is described that defines the set of real-valued matrices, for which a solution to the assignment problem with one fixed assignment gives an upper bound for the optimum value of the traveling salesman problem (TSP). This allows one to extend the result obtained for the TSP on strictly-upper-triangular matrices, for which E. Lawler has proved the polynomial solvability of the TSP.