scientific article; zbMATH DE number 3630482

MaRDI QIDQ4191856zbMATH OpenFDO

Authors Alan Frieze

Publication date 1979

zbMATH Keywords

Computational ComplexityGreedy AlgorithmHeuristic AlgorithmSymmetric Travelling Salesman ProblemWorst-Case Behaviour

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10)

Cited in

(8)

• Approximation algorithms for the Geometric Covering Salesman Problem
• The approximation ratio of the greedy algorithm for the metric traveling salesman problem
• Asymptotic expected performance of some TSP heuristics: An empirical evaluation
• An extension of Christofides heuristic to the k-person travelling salesman problem
• Strategies for generating well centered tetrahedral meshes on industrial geometries
• Minimum-weight two-connected spanning networks
• Truly tight bounds for TSP heuristics
• Worst-case analysis of two travelling salesman heuristics

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4191856)