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.

Related Publications

All Publications

ICML - July 24, 2021

Ditto: Fair and Robust Federated Learning Through Personalization

Tian Li, Shengyuan Hu, Ahmad Beirami, Virginia Smith

International Workshop on Realizing Artificial Intelligence Synergies in Software Engineering (RAISE) - September 26, 2021

Behavioural and Structural Imitation Models in Facebook’s WW Simulation System

John Ahlgren, Kinga Bojarczuk, Inna Dvortsova, Mark Harman, Rayan Hatout, Maria Lomeli, Erik Meijer, Silvia Sapora

ESEM - September 23, 2021

Measurement Challenges for Cyber Cyber Digital Twins: Experiences from the Deployment of Facebook’s WW Simulation System

Kinga Bojarczuk, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Simon Mark Lucas, Erik Meijer, Rubmary Rojas, Silvia Sapora

Federated Learning for User Privacy and Data Confidentiality Workshop At ICML - July 24, 2021

Federated Learning with Buffered Asynchronous Aggregation

John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Michael Rabbat, Mani Malek, Dzmitry Huba

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy