The Location Problem on a Line With Forbidden Region Constraint
Guangting Chen · 2004
Let L be a straight line in an Euclidean plane, and N be a set of n points on the same side of L, F be a forbidden region in L consisting of some intervals. The problem is to find a point P in L outside F such that the length of the network interconnecting the set N∪｛p｝ is minimized. An O(n~2) approximation algorithm is presented, whose performance ratio is shown to be 32 .