Innovative Techniques for Constructing Branch Decompositions

构建分支分解的创新技术

• 批准号: 0729251
• 负责人: Illya Hicks
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-12-31 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729251&HistoricalAwards=false
• 关键词: Innovative; Techniques; Constructing; Branch; Decompositions

This grant provides funding for the development of novel numerical techniques to solve computationally hard mathematical problems in combinatorial optimization that have relevant applications in network design, sensor networks, and biology. The developed techniques will be used to increase the scalability of problems solved in these research areas. Specifically, the research will develop innovative techniques to produce a specific but vital decomposition structure, called a branch decomposition, for mathematical structures called graphs that are used to mathematically model these problems. To this end, the developed techniques will be compared with other exact algorithms in the literature to validate and assess the computational efficacy of the techniques. If successful, the results will increase the scalability and efficiency of solving the problems of interest. Applications of these problems are in fields seeing increased demand for services. In addition, the results can be used to solve other related computationally hard problems in combinatorial optimization which have a wide range of applications apart from the aforementioned applications. Thus, the results will advance the knowledge base in combinatorial optimization and offer new effective techniques for solving large-scale problems in the areas.

该基金为新型数值技术的发展提供资金，以解决在网络设计、传感器网络和生物学中有相关应用的组合优化中计算困难的数学问题。所开发的技术将用于提高这些研究领域所解决问题的可扩展性。具体地说，这项研究将开发创新的技术，以产生一种特定但重要的分解结构，称为分支分解，用于数学结构，称为图，用于数学建模这些问题。为此，将开发的技术与文献中的其他精确算法进行比较，以验证和评估这些技术的计算效率。如果成功，结果将提高解决感兴趣问题的可伸缩性和效率。这些问题的应用是在对服务需求增加的领域。此外，所得结果可用于解决组合优化中除上述应用外具有广泛应用范围的其他相关计算难题。因此，该结果将进一步完善组合优化的知识库，并为解决该领域的大规模问题提供新的有效技术。