Premium
Continuous approximation formulas for location problems
Author(s) -
Carlsson John Gunnar,
Jones Bo
Publication year - 2022
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22099
Subject(s) - travelling salesman problem , minimum spanning tree , vehicle routing problem , mathematical optimization , routing (electronic design automation) , approximation algorithm , mathematics , spanning tree , computer science , tree (set theory) , constant (computer programming) , algorithm , combinatorics , computer network , programming language
The majority of research in the continuous approximation paradigm has emphasized routing problems, such as the travelling salesman problem and the vehicle routing problem. This article instead focuses on continuous approximation formulas for problems involving location, specifically thek $$ k $$ ‐medians,k $$ k $$ ‐dispersion, and generalized minimum spanning tree problems. We contribute bounds for constants that describe the growth rate of the cost of these problems as the number of demand points becomes large, and conduct computational experiments that verify that they provide a good approximation in practice.