Why should we pay more for layout designers?

摘要

In this paper, we discuss the Passive Optical Network deployment on an arbitrary grid with guaranteed tolerance towards p-1 equipment failure. We show that this problem in general is NP-hard. We propose an algorithm, which guarantees a solution of 4-approximation to the optimal deployment, and further argue that this is the best lower bound achievable in our case. We do comparative studies with randomized layouts, were our proposed algorithm saves 45%-55% deployment cost (fiber, equipment, etc) on average.