A rounding algorithm for approximating minimum Manhattan networks

DOI10.1016/J.TCS.2007.10.013MaRDI QIDQ2474072zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Yann Vaxès, Karim Nouioua

Publication date 5 March 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.10.013

zbMATH Keywords

linear programmingapproximation algorithmsnetwork design\(l_1\)-distance

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1979512
• The minimum Manhattan network problem: Approximations and exact solutions
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Greedy construction of 2-approximate minimum Manhattan networks

Cites work

• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A catalog of Hanan grid problems
• Algorithms and Computation
• Approximating a minimum Manhattan network
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Finding efficient solutions for rectilinear distance location problems efficiently
• Geometric Spanner Networks
• Subclass of the Steiner problems on a plane with rectilinear metric
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• The minimum Manhattan network problem: Approximations and exact solutions
• The rectilinear Steiner arborescence problem

Cited in

(14)

• Searching for realizations of finite metric spaces in tight spans
• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• On minimum generalized Manhattan connections
• The Minimal Manhattan Network Problem in Three Dimensions
• Approximating the generalized minimum Manhattan network problem
• Linear-size planar Manhattan network for convex point sets
• Bidirected minimum Manhattan network problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Pareto envelopes in simple polygons
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Minimum Manhattan network is NP-complete

This page was built for publication: A rounding algorithm for approximating minimum Manhattan networks

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