Algorithms for Approximate Routing Problems

点击翻译按钮获取中文摘要

The research in this proposal aims to advance fundamentalknowledge of routing methods that trade off optimality in return forspace, time, locality, fault-tolerance, and adaptability to changingnetwork topology. The study of multi-criteria routing problems is alsocommenced, where for even the most natural and simply-stated multi-criteriarouting problems, there are typically only heuristics known. The goalis to produce methods that trade off some optimality of the solutionin returned for lowered computational resurces, in a quantifiable way. Approximate shortest-paths, compact routing, and distance labelingproblems will be studied, along with their extensions to directednetworks, dynamic networks, and multi-criteria formulations incorporating different tradeoffs of time and space with measures ofrisk and reliability.