Worst-case analysis of a new heuristic for the travelling salesman problem
From MaRDI portal
Publication:2120141
DOI10.1007/s43069-021-00101-zzbMath1489.90150OpenAlexW2117226423MaRDI QIDQ2120141
Publication date: 31 March 2022
Published in: SN Operations Research Forum (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s43069-021-00101-z
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (57)
In memoriam: Nicos Christofides (1942--2019) ⋮ Optimizing Read Reversals for Sequence Compression ⋮ A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring ⋮ Metric violation distance: hardness and approximation ⋮ Novel concave hull-based heuristic algorithm for TSP ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Maximizing energy efficiency for charger scheduling of WRSNs ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Approximating the Minimum Tour Cover with a Compact Linear Program ⋮ The simultaneous semi-random model for TSP ⋮ Matroid-based TSP rounding for half-integral solutions ⋮ The parameterized complexity of local search for TSP, more refined ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ On the approximability of the maximum common subgraph problem ⋮ A partitioning column approach for solving LED sorter manipulator path planning problems ⋮ Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ Heuristic sequencing methods for time optimal tracking of nested, open and closed paths ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ A one pass streaming algorithm for finding Euler tours ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Ordered scheduling in control-flow distributed transactional memory ⋮ Time complexity of the analyst's traveling salesman algorithm ⋮ Approximation Algorithms for Barrier Sweep Coverage ⋮ Tour recommendation for groups ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Online covering salesman problem ⋮ The travelling salesman and the PQ-tree ⋮ One-to-Many-to-One Single Vehicle Pickup and Delivery Problems ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ DNA origami and the complexity of Eulerian circuits with turning costs ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ On the Hardness of Reoptimization ⋮ The Power of Recourse for Online MST and TSP ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Continuous relaxations for the traveling salesman problem ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Scheduling ships movements within a canal harbor ⋮ Computing in combinatorial optimization ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Unnamed Item ⋮ A greedy algorithm for finding maximum spanning trees in infinite graphs ⋮ Approximating minimum-cost connected \(T\)-joins ⋮ Approximation algorithms for solving the heterogeneous Chinese postman problem
Cites Work
This page was built for publication: Worst-case analysis of a new heuristic for the travelling salesman problem
