DSpace Repository

A rounding algorithm for approximating minimum Manhattan networks

Show simple item record

dc.contributor.author CHEPOI, Victor
dc.contributor.author NOUIOUA, Karim
dc.contributor.author VAXÈS, Carim
dc.date.accessioned 2020-06-12T12:06:22Z
dc.date.available 2020-06-12T12:06:22Z
dc.date.issued 2005
dc.identifier.citation CHEPOI, Victor, NOUIOUA, VAXÈS Karim. A rounding algorithm for approximating minimum Manhattan networks. In: Microelectronics and Computer Science: proc. of the 4th intern. conf., September 15-17, 2005. Chişinău, 2005, vol. 2, pp. 16-22. ISBN 9975-66-038-X. en_US
dc.identifier.issn 9975-66-038-X
dc.identifier.uri http://repository.utm.md/handle/5014/8906
dc.description.abstract For a set T of n points (terminals) in the plane, a Manhattan network on T is a network N(T)=(V,E) with the property that its edges are horizontal or vertical segments connecting points in V ⊇ T and for every pair of terminals, the network N(T) contains a shortest l 1-path between them. A minimum Manhattan network on T is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) and it is not known whether this problem is in P or not. Several approximation algorithms (with factors 8,4, and 3) have been proposed; recently Kato, Imai, and Asano (ISAAC’02) have given a factor 2 approximation algorithm, however their correctness proof is incomplete. In this note, we propose a rounding 2-approximation algorithm based on a LP-formulation of the minimum Manhattan network problem.
dc.language.iso en en_US
dc.publisher Technical University of Moldova en_US
dc.rights Attribution-NonCommercial-NoDerivs 3.0 United States *
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/us/ *
dc.subject Manhattan networks en_US
dc.subject vertical segment
dc.subject horizontal strip
dc.title A rounding algorithm for approximating minimum Manhattan networks en_US
dc.type Article en_US


Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 United States Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States

Search DSpace


Advanced Search

Browse

My Account