A PTAS for the geometric connected facility location problem

DOI10.1007/s00224-017-9749-xzbMath1372.90066OpenAlexW2584803184MaRDI QIDQ2408564

Renata G. D. de Souza, Flávio K. Miyazawa, Rafael C. S. Schouery, Lehilton L. C. Pedrosa

Publication date: 12 October 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9749-x

zbMATH Keywords

polynomial-time approximation schemeconnected facility location problemprize-collectinggeometric problem

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• Primal-dual algorithms for connected facility location problems
• Approximation schemes for node-weighted geometric Steiner tree problems
• Euclidean prize-collecting Steiner forest
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• How Long Can a Euclidean Traveling Salesman Tour Be?
• A General Approximation Technique for Constrained Forest Problems
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Provisioning a virtual private network
• Steiner Minimal Trees

This page was built for publication: A PTAS for the geometric connected facility location problem