Algorithms for Approximate Routing Problems

近似路由问题的算法

• 批准号: 0208629
• 负责人: Lenore Cowen
• 金额: $ 22.26万
• 依托单位: Tufts University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-06-01 至 2006-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208629&HistoricalAwards=false
• 关键词: Algorithms; 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.

本提案的研究旨在提高路由方法的基本知识，以换取空间、时间、局域性、容错和对网络拓扑变化的适应性的最优性。多准则路由问题的研究也开始了，即使是最自然和最简单的多准则路由问题，通常也只有启发式已知。其目标是以一种可量化的方式，以较低的计算资源换取解决方案的一些最优性。将研究近似最短路径，紧凑路由和距离标记问题，以及它们对定向网络，动态网络和多标准公式的扩展，这些公式结合了时间和空间的不同权衡以及风险和可靠性的措施。