The minimum Manhattan network problem: Approximations and exact solutions

DOI10.1016/j.comgeo.2005.09.004zbMath1144.90319MaRDI QIDQ2432734

Alexander Wolff, Takeshi Shirabe, Florian Widmann, Marc Benkert

Publication date: 25 October 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2005.09.004

zbMATH Keywords

approximation algorithm; mixed-integer programming; spanners; minimum manhattan networks

Mathematics Subject Classification ID

90C11: Mixed integer programming

90B10: Deterministic network models in operations research

68W25: Approximation algorithms

Related Items

Light Euclidean Spanners with Steiner Points, Minimum Manhattan network is NP-complete, Linear-size planar Manhattan network for convex point sets, The transitive minimum Manhattan subnetwork problem in 3 dimensions, Light orthogonal networks with constant geometric dilation, Exact algorithms for the order picking problem, Searching for realizations of finite metric spaces in tight spans, Approximating minimum Manhattan networks in higher dimensions, Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm, The minimum Manhattan network problem: Approximations and exact solutions, A rounding algorithm for approximating minimum Manhattan networks, GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS, A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem, The Minimal Manhattan Network Problem in Three Dimensions

Cites Work

• There are planar graphs almost as good as the complete graph
• The minimum Manhattan network problem: Approximations and exact solutions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item