Bottleneck Problems: Analysis and 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.