A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
From MaRDI portal
Publication:3511430
DOI10.1007/978-3-540-68880-8_21zbMath1143.68638OpenAlexW1798156434MaRDI QIDQ3511430
Publication date: 10 July 2008
Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-68880-8_21
Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items
On minimum generalized Manhattan connections, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane, Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm, Minimum Manhattan network is NP-complete, Searching for realizations of finite metric spaces in tight spans
Cites Work
- Unnamed Item
- Unnamed Item
- Finding efficient solutions for rectilinear distance location problems efficiently
- The minimum Manhattan network problem: Approximations and exact solutions
- A rounding algorithm for approximating minimum Manhattan networks
- The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
- Algorithms and Computation