返回Google圖書搜尋

Minimum-length Corridors

其他書名	Complexity and Approximations
出版	University of California, Santa Barbara, 2007
ISBN	05492681549780549268154
URL	http://books.google.com.hk/books?id=_dG0swEACAAJ&hl=&source=gbs_api

註釋Tricts the solution space by limiting in each room the possible vertices, from which at least one must be part of the corridor. The resulting problem, which remains NP-complete, is solved by relaxing the set of feasible solutions. Then the solution is rounded and solves the original problem instance. This approach is adapted to the rectangular group-TSP, resulting in a constant ratio approximation algorithm. The approximation scheme can also be applied to the MLCk problem, i.e., the MLC problem when every room is a rectilinear c-gon, for c & ge; k, but the approximation ratio depends on k. A polynomial time constant ratio approximation algorithm for the group-TSP for a rectangular boundary partitioned into rectilinear c-gons, as in the MLCk problem when k is a constant, is presented. An application for the MLC problem is when laying optical fiber in metropolitan areas and every block (or set of blocks) is connected through its own gateway. The objective is to find a minimum-length cor.