2026-07-26T19:18:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15475 2024-03-06T10:55:23Z ddc:004 open_access

On the Extended TSP Problem Mestre, Julián Pupyrev, Sergey Umboh, Seeun William profile-guided optimization approximation algorithms bandwidth TSP 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 f(⋅) such that f(1) = 1 and f(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} f(|d_u - d_v|)⋅ w(u,v), where d_v ∈ {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 n^o(k) time algorithm for trees unless the ETH fails. We complement this negative result with an exact n^O(k) time algorithm for trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julián Mestre and Sergey Pupyrev and Seeun William Umboh 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.42 urn:nbn:de:0030-drops-154751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.42 eng https://creativecommons.org/licenses/by/4.0/legalcode