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.