A PTAS for the geometric connected facility location problem

DOI10.1007/S00224-017-9749-XMaRDI QIDQ2408564zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Approximation algorithms for connected facility location problems
• Improved Approximation Algorithm for Connected Facility Location Problems
• Securely connected facility location in metric graphs
• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• Primal-dual algorithms for connected facility location problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 6297716 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• Approximation schemes for node-weighted geometric Steiner tree problems
• Euclidean prize-collecting Steiner forest
• 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?
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Primal-dual algorithms for connected facility location problems
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Steiner Minimal Trees

Cited in

(2)

• On PTAS for the geometric maximum connected k-factor problem
• On the Asymmetric Connected Facility Location Polytope

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

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