Bottleneck Problems: Analysis and Approximations

瓶颈问题：分析和近似

• 批准号: 8501988
• 负责人: Dorit Hochbaum
• 金额: $ 11.31万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1985
• 资助国家: 美国
• 起止时间: 1985-07-01 至 1988-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8501988&HistoricalAwards=false
• 关键词: Bottleneck; Problems; Analysis; Approximations

This research will concentrate on two approaches for analyzing the effectiveness of algorithms for a class of significant hard optimization problems -- the bottleneck problems -- with applications to location theory, routing, and communication network design. These approaches are probabilistic analysis of heuristic algorithms, and worst case analysis of heuristic algorithms. Although these approaches are often considered theoretical in nature, they can have profound practical implications. Currently, algorithm design is largely an ad hoc procedure, whether the goal is to analyze the algorithm based on its expected or worst case performance, or to provide bounding procedures within a branch-and-bound context. The aims of this research are to study the bottleneck problems from several different viewpoints and to devise unified techniques rather than separate, haphazard problem-dependent methods.

本研究将集中在两种方法来分析 一类有意义困难问题算法的有效性 最优化问题--瓶颈问题--及其应用 定位理论、路由和通信网络设计。 这些 方法是启发式算法的概率分析， 启发式算法的最坏情况分析。 尽管这些方法 通常被认为是理论性的，它们可能具有深刻的 实际影响。 目前，算法设计在很大程度上是 hoc程序，目标是否是分析算法的基础 其预期或最差情况下的性能，或提供边界 在一个分支和绑定的上下文中。 其目的是 研究是从几个不同的研究瓶颈问题 观点和设计统一的技术，而不是分开， 随机问题依赖方法。