A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem

DOI10.1007/978-3-540-68880-8_21zbMath1143.68638OpenAlexW1798156434MaRDI QIDQ3511430

He Sun, Hong Zhu, Zeyu Guo

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

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (5)

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

This page was built for publication: A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem