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.