Research output per year
Research output per year
Research output: Contribution to journal › Article › Academic › peer-review
The Graphical Traveling Salesperson Problem is the problem of assigning, for a given weighted graph, a nonnegative number xe to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Known MIP formulations are based on integer variables xe. Carr and Simonetti (IPCO 2021) showed that unless NP=coNP, no (reasonable) formulation can have integrality constraints only on x-variables, a challenge posed by Denis Naddef. We establish the same result unconditionally.
Original language | English |
---|---|
Pages (from-to) | 623-624 |
Number of pages | 2 |
Journal | Operations research letters |
Volume | 49 |
Issue number | 4 |
DOIs | |
Publication status | Published - Jul 2021 |
Research output: Working paper › Preprint › Academic