Cover Image

Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	O'Hara, Patrick, Ramanujan, M. S., Damoulas, Theodoros
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

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

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2020)

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

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)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
by: Blažej, Václav, et al.
Published: (2024)

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

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
by: Mallek, Nadym, et al.
Published: (2025)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
by: Blauth, Jannis, et al.
Published: (2022)

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

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

Efficient Trace Frequency Queries in Sparse Graphs
by: Awofeso, Christine, et al.
Published: (2025)

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

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
by: Ahmadi, Ali, et al.
Published: (2025)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

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

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

Cost-Distance Steiner Trees for Timing-Constrained Global Routing
by: Held, Stephan, et al.
Published: (2025)

The En Route Truck-Drone Delivery Problem
by: Krizanc, Danny, et al.
Published: (2024)

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

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

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

Canadian Traveller Problems in Temporal Graphs
by: Bellitto, Thomas, et al.
Published: (2024)

Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
by: Szyfelbein, Michał
Published: (2025)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Temporal Routing in Static Networks: The Schedule Completion Problem
by: Döring, Michelle, et al.
Published: (2026)

Tractable Graph Structures in EFX Orientation
by: Blažej, Václav, et al.
Published: (2025)

Improved FPT Approximation for Non-metric TSP
by: Bampis, Evripidis, et al.
Published: (2024)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

Listing 6-Cycles in Sparse Graphs
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)

Split Algorithm in Linear Time for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows
by: Gibbons, Ethan, et al.
Published: (2026)

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

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
by: Azar, Yossi, et al.
Published: (2025)

Algebraic Vertex Ordering of a Sparse Graph for Adjacency Access Locality and Graph Compression
by: Floros, Dimitris, et al.
Published: (2024)