Cover Image

Improved FPT Approximation for Non-metric TSP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bampis, Evripidis, Escoffier, Bruno, Xefteris, Michalis
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
by: Bampis, Evripidis, et al.
Published: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

FPT Approximations for Fair $k$-Min-Sum-Radii
by: Carta, Lena, et al.
Published: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

4/3-Approximation of Graphic TSP
by: Çivril, Ali
Published: (2023)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
by: Manurangsi, Pasin
Published: (2024)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
by: Baligács, Júlia, et al.
Published: (2024)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
by: Lanzinger, Matthias, et al.
Published: (2023)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
by: Christalla, Manuel, et al.
Published: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
by: Blauth, Jannis, et al.
Published: (2023)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

An FPT algorithm for Matching Cut and d-cut
by: Aravind, N R, et al.
Published: (2021)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Online Metric TSP
by: Bertram, Christian
Published: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
by: Saller, Sophia, et al.
Published: (2023)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
by: Berthe, Gaétan, et al.
Published: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
by: Krithika, R., et al.
Published: (2025)

Dual Charging for Half-Integral TSP
by: Klein, Nathan, et al.
Published: (2025)

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
by: Mestel, David, et al.
Published: (2024)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
by: Armbruster, Alexander, et al.
Published: (2026)