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; 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.

该提案中的研究旨在提高路由方法的基础知识，以换取最优性，以回报空间，时间，区域，耐断层耐受性以及更改网络拓扑的适应性。多标准路由问题的研究是有准入的，即使是最自然，最简单的多监视问题，通常也只有启发式方法。目的是生产方法以量化的方式返回的解决方案的某种最佳解决方案的方法。将研究近似最短的路径，紧凑的路由和距离标记问题，并将其扩展到指导性网络，动态网络和多标准公式，并融合了带有环境和可靠性的时间和空间的不同权衡。