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

DOI10.1007/978-3-540-68880-8_21MaRDI QIDQ3511430zbMATH OpenOpenAlexFDO

Authors Zeyu Guo, He Sun, Hong Zhu

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)

Recommendations

• Greedy construction of 2-approximate minimum Manhattan networks
• Greedy Construction of 2-Approximation Minimum Manhattan Network
• scientific article; zbMATH DE number 1979512
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• A rounding algorithm for approximating minimum Manhattan networks
• Algorithms and Computation
• Approximating a minimum Manhattan network
• Finding efficient solutions for rectilinear distance location problems efficiently
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• The minimum Manhattan network problem: Approximations and exact solutions

Cited in

(19)

• The two‐median problem on Manhattan meshes
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• On minimum generalized Manhattan connections
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Minimum Manhattan network is NP-complete
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Greedy construction of 2-approximate minimum Manhattan networks
• Searching for realizations of finite metric spaces in tight spans
• A fixed-parameter algorithm for the minimum Manhattan network problem
• A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
• A shortest-path algorithm for Manhattan graphs
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• Minimum Manhattan network is NP-complete
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Approximating a minimum Manhattan network
• Algorithms and Computation
• Greedy Construction of 2-Approximation Minimum Manhattan Network

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

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