On the Extended TSP Problem

International Symposium on Algorithms and Computation (ISAAC )


We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph G = (V, E) with positive edge weights w : E→R+ , and a non-increasing discount function ƒ (·) such that ƒ (1) = 1 and ƒ (i) = 0 for i > k, for some parameter k that is part of the problem definition. The problem is to sequence the vertices V so as to maximize ∑(u, v)∈E ƒ(|du — dv |) ⋅ w (u, v ), where dv ∈ {1, . . . , |V|} is the position of vertex v in the sequence.

We show that Ext-TSP is APX-hard to approximate in general and we give a (k + 1)- approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs.

Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact no (k) time algorithm for trees unless the ETH fails. We complement this negative result with an exact nO(k) time algorithm for trees.

Latest Publications

Sustainable AI: Environmental Implications, Challenges and Opportunities

Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga Behram, James Huang, Charles Bai, Michael Gschwind, Anurag Gupta, Myle Ott, Anastasia Melnikov, Salvatore Candido, David Brooks, Geeta Chauhan, Benjamin Lee, Hsien-Hsin S. Lee, Bugra Akyildiz, Max Balandat, Joe Spisak, Ravi Jain, Mike Rabbat, Kim Hazelwood

MLSys - 2022