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.

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