Buchumschlag

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Zhao, Jingyang, Sheng, Zimo, Xiao, Mingyu
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Improved Approximation Algorithm for Metric Triangle Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
von: Zhao, Jingyang, et al.
Veröffentlicht: (2022)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

Improved Approximations for Dial-a-Ride Problems
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

New Algorithms for #2-SAT and #3-SAT
von: Peng, Junqiang, et al.
Veröffentlicht: (2025)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2024)

The APX-hardness of the Traveling Tournament Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
von: Liu, Yuxi, et al.
Veröffentlicht: (2023)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
von: Ren, Kinter, et al.
Veröffentlicht: (2024)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
von: Xiong, Ziliang, et al.
Veröffentlicht: (2024)

Improved FPT Approximation for Non-metric TSP
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

Online Metric TSP
von: Bertram, Christian
Veröffentlicht: (2025)

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

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

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
von: Liu, Yuxi, et al.
Veröffentlicht: (2026)

Approximating Prize-Collecting Variants of TSP
von: Alimi, Morteza, et al.
Veröffentlicht: (2024)

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)

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

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

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

Faster Parameterized Vertex Multicut
von: Chu, Huairui, et al.
Veröffentlicht: (2026)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
von: Christalla, Manuel, et al.
Veröffentlicht: (2025)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
von: Zhao, Zhuowei, et al.
Veröffentlicht: (2025)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2023)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
von: Feldmann, Andreas Emil, et al.
Veröffentlicht: (2024)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
von: Blauth, Jannis, et al.
Veröffentlicht: (2023)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
von: Mo, Guanlin, et al.
Veröffentlicht: (2024)

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

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)