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

Zeyu Guo; He Sun; Hong Zhu

doi:10.1007/978-3-540-68880-8_21

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

Zeyu Guo, He Sun, Hong Zhu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a set T of n points in ℝ², a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n ²), which improves the 2-approximation algorithm with time complexity Ω(n ⁸), proposed by Chepoi, Nouioua et al.. To the best of our knowledge, this is the best result on this problem.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings
Pages	212-223
Number of pages	12
ISBN (Electronic)	978-3-540-68880-8
DOIs	https://doi.org/10.1007/978-3-540-68880-8_21
Publication status	Published - 2008
Event	4th International Conference on Algorithmic Aspects in Information and Management - Shanghai, China Duration: 23 Jun 2008 → 25 Jun 2008

Conference

Conference	4th International Conference on Algorithmic Aspects in Information and Management
Abbreviated title	AAIM 2008
Country/Territory	China
City	Shanghai
Period	23/06/08 → 25/06/08

Access to Document

10.1007/978-3-540-68880-8_21

https://link.springer.com/chapter/10.1007%2F978-3-540-68880-8_21#aboutcontent

Cite this

@inproceedings{cdc197efe67649c5be5c3dbc35c9aa5d,

title = "A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem",

abstract = "Given a set T of n points in ℝ2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n 2), which improves the 2-approximation algorithm with time complexity Ω(n 8), proposed by Chepoi, Nouioua et al.. To the best of our knowledge, this is the best result on this problem.",

author = "Zeyu Guo and He Sun and Hong Zhu",

year = "2008",

doi = "10.1007/978-3-540-68880-8_21",

language = "English",

isbn = "978-3-540-68865-5",

pages = "212--223",

booktitle = "Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings",

note = "4th International Conference on Algorithmic Aspects in Information and Management, AAIM 2008 ; Conference date: 23-06-2008 Through 25-06-2008",

}

Guo, Z, Sun, H & Zhu, H 2008, A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem. in Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings. pp. 212-223, 4th International Conference on Algorithmic Aspects in Information and Management, Shanghai, China, 23/06/08. https://doi.org/10.1007/978-3-540-68880-8_21

TY - GEN

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

AU - Guo, Zeyu

AU - Sun, He

AU - Zhu, Hong

PY - 2008

Y1 - 2008

N2 - Given a set T of n points in ℝ2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n 2), which improves the 2-approximation algorithm with time complexity Ω(n 8), proposed by Chepoi, Nouioua et al.. To the best of our knowledge, this is the best result on this problem.

AB - Given a set T of n points in ℝ2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network (MMN) problem is to find a Manhattan network of the minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n 2), which improves the 2-approximation algorithm with time complexity Ω(n 8), proposed by Chepoi, Nouioua et al.. To the best of our knowledge, this is the best result on this problem.

U2 - 10.1007/978-3-540-68880-8_21

DO - 10.1007/978-3-540-68880-8_21

M3 - Conference contribution

SN - 978-3-540-68865-5

SP - 212

EP - 223

BT - Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings

T2 - 4th International Conference on Algorithmic Aspects in Information and Management

Y2 - 23 June 2008 through 25 June 2008

ER -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this