Abstract:

A large variety of scheduling problems has recently been identified as special cases of the Traveling Salesman Problem (TSP) on permuted Monge matrices. Although the TSP on permuted Monge matrices is known to be strongly NP-hard, we show that polynomial-time solutions exist for many of the special cases generated by the scheduling problems. We also show that a simple subtour-patching heuristic is asymptotically optimal for the TSP on permuted Monge matrices under some mild technical conditions.