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 |
The following license files are associated with this item: