scientific article; zbMATH DE number 7378685
From MaRDI portal
Publication:5009572
DOI10.4230/LIPIcs.ESA.2018.15zbMath1484.68330arXiv1710.07774MaRDI QIDQ5009572
No author found.
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1710.07774
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Steiner treedoubling dimensionpolynomial-time approximation schemeprize-collecting traveling salesman problem
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (2)
FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM ⋮ Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
Cites Work
- A note on the prize collecting traveling salesman problem
- Nearest neighbor queries in metric spaces
- Euclidean prize-collecting Steiner forest
- The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Bypassing the embedding
- Plongements lipschitziens dans ${\bbfR}\sp n$
- The prize collecting traveling salesman problem
- Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
- A General Approximation Technique for Constrained Forest Problems
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Geometry of cuts and metrics
- Unnamed Item
- Unnamed Item
This page was built for publication:
