Solving a "Hard" problem to approximate an "Easy" one

DOI10.1145/944618.944629zbMath1069.90116OpenAlexW2152727633MaRDI QIDQ5463433

Sándor P. Fekete, Walter Tietze, André Rohe, Henk G. Meijer

Publication date: 4 August 2005

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: http://www.jea.acm.org/2002/FeketeHeuristics/

zbMATH Keywords

maximum weighted matchingFermat-Weber problemgeometric problemsnear-linear algorithmsmaximum Traveling Salesman Problem (MTSP)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours

Uses Software

• TSPLIB