A rounding algorithm for approximating minimum Manhattan networks

DOI10.1016/J.TCS.2007.10.013zbMATH Open1209.90069OpenAlexW2134026356MaRDI QIDQ2474072FDOQ2474072

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

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

zbMATH Keywords

linear programmingapproximation algorithmsnetwork design\(l_1\)-distance

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• Linear-size planar Manhattan network for convex point sets
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On minimum generalized Manhattan connections
• Minimum Manhattan network is NP-complete
• Approximating the generalized minimum Manhattan network problem
• Searching for realizations of finite metric spaces in tight spans
• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• Approximating minimum Manhattan networks in higher dimensions
• Title not available (Why is that?)
• 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
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• The Minimal Manhattan Network Problem in Three Dimensions
• Bidirected minimum Manhattan network problem
• Pareto envelopes in simple polygons

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)