On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
From MaRDI portal
Publication:3936521
DOI10.1002/net.3230120103zbMath0478.90070OpenAlexW2035610952WikidataQ57401646 ScholiaQ57401646MaRDI QIDQ3936521
Giulia Galbiati, Francesco Maffioli, Alan M. Frieze
Publication date: 1982
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230120103
worst-case performanceasymmetric traveling salesman problemcomparison of heuristic algorithmsn city problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)
Related Items
On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem, Traveling salesman problems in temporal graphs, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Towards auction algorithms for large dense assignment problems, LP-based solution methods for the asymmetric TSP, Improved length bounds for the shortest superstring problem, A survey on combinatorial optimization in dynamic environments, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, Constant Factor Approximation for ATSP with Two Edge Weights, An Improved Integrality Gap for Asymmetric TSP Paths, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem, The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis, Lower and upper competitive bounds for online directed graph exploration, Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, On the relationship between ATSP and the cycle cover problem, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem, A simple LP relaxation for the asymmetric traveling salesman problem, Time-approximation trade-offs for inapproximable problems, A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem, A bound for the symmetric travelling salesman problem through matroid formulation, A study of complexity transitions on the asymmetric traveling salesman problem, Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems, Polyhedral techniques in combinatorial optimization: matchings and tours, Improved approximation algorithm for the asymmetric prize-collecting TSP, A primal-dual approximation algorithm for the asymmetric prize-collecting TSP, Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles, A note on the approximation of the asymmetric traveling salesman problem., Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems, Approximately fair cost allocation in metric traveling salesman games, The Directed Minimum Latency Problem, A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, The on-line asymmetric traveling salesman problem, Approximating the minimum tour cover of a digraph, Dubins traveling salesman problem with neighborhoods: a graph-based approach, Quell, Analysis of the Held-Karp lower bound for the asymmetric TSP, Traveling salesman path problems, APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Complexity of the directed spanning cactus problem, The directed orienteering problem, Unnamed Item, Asymmetry in \(k\)-center variants, Minimum-weight two-connected spanning networks, No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem, The temporal explorer who returns to the base, Constant factor approximation for ATSP with two edge weights, Heuristic methods and applications: A categorized survey, A \(2_3^2\) superstring approximation algorithm, An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
Cites Work
