The Generalisation of Cutler and Shiloahâ€™s Algorithm for Routing
Julia Chuzhoy and David H. K. Kim
Progress in Signals and Telecommunication Engineering, Vol. 13, No. 1, 2024.
DOI: https://doi.org/10.6025/pste/2024/13/1/18-43
Link: https://www.dline.info/pste/fulltext/v13n1/pstev13n1_2.pdf
Abstract:
This paper generalizes Cutler and Shiloahâ€™s algorithm for routing with well-separated destinations. We provide an O(n1/4Â· log n) approximation algorithm for NDP on grids and give the APX-hardness proof. In this work, we discuss the integrality gap of the multicommodity flow LP relaxation when all terminals are far from the grid boundary.