Cover Image

Approximating Traveling Salesman Problems Using a Bridge Lemma

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Böhm, Martin, Friggstad, Zachary, Mömke, Tobias, Spoerhase, Joachim
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

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

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

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)

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

A faster heuristic for the Traveling Salesman Problem with Drone
by: Hokama, Pedro H. D. B., et al.
Published: (2024)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
by: DeHaan, Ian, et al.
Published: (2024)

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

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Improving polynomial bounds for the Graphical Traveling Salesman Problem with release dates on paths
by: Clementino, Thailsson, et al.
Published: (2025)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

C*: A New Bounding Approach for the Moving-Target Traveling Salesman Problem
by: Philip, Allen George, et al.
Published: (2023)

A QPTAS for Facility Location on Unit Disk graphs
by: Friggstad, Zachary, et al.
Published: (2024)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems
by: Wang, Long, et al.
Published: (2025)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
by: Ghaseminia, Benyamin, et al.
Published: (2025)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
by: Herold, Martin G., et al.
Published: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
by: Philip, Allen George, et al.
Published: (2024)

The Canadian Traveller Problem on outerplanar graphs
by: Beaudou, Laurent, et al.
Published: (2024)

The APX-hardness of the Traveling Tournament Problem
by: Zhao, Jingyang, et al.
Published: (2023)

Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
by: Friggstad, Zachary, et al.
Published: (2018)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
by: Peng, Cheng, et al.
Published: (2024)

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
by: Deng, Chengyuan, et al.
Published: (2025)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

Approximate Counting in Local Lemma Regimes
by: Mann, Ryan L., et al.
Published: (2025)

Improved Approximations for Dial-a-Ride Problems
by: Zhao, Jingyang, et al.
Published: (2026)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
by: Blais, Eric, et al.
Published: (2024)

Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem
by: O'Hara, Patrick, et al.
Published: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)

3/2-Approximation for the Forest Augmentation Problem
by: Çivril, Ali
Published: (2024)