The minimum Manhattan network problem: Approximations and exact solutions

DOI10.1016/J.COMGEO.2005.09.004MaRDI QIDQ2432734zbMATH OpenOpenAlexFDO

Authors Marc Benkert, Alexander Wolff, Florian Widmann, Takeshi Shirabe

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 algorithmminimum manhattan networksmixed-integer programmingspanners

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Mixed integer programming (90C11)

Recommendations

• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Approximating a minimum Manhattan network
• Greedy Construction of 2-Approximation Minimum Manhattan Network
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Algorithms and Computation

Cites work

• Approximating a minimum Manhattan network
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• The minimum Manhattan network problem: Approximations and exact solutions
• There are planar graphs almost as good as the complete graph

Cited in

(19)

• Light orthogonal networks with constant geometric dilation
• Exact algorithms for the order picking problem
• Searching for realizations of finite metric spaces in tight spans
• 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
• Approximating a minimum Manhattan network
• Greedy construction of 2-approximate minimum Manhattan networks
• Geometric Spanner of Objects under L 1 Distance
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Greedy Construction of 2-Approximation Minimum Manhattan Network
• The Minimal Manhattan Network Problem in Three Dimensions
• Minimum Manhattan network is NP-complete
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Light Euclidean Spanners with Steiner Points
• Algorithms and Computation
• Linear-size planar Manhattan network for convex point sets
• The transitive minimum Manhattan subnetwork problem in 3 dimensions

This page was built for publication: The minimum Manhattan network problem: Approximations and exact solutions

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