Approximation Algorithms for Combinatorial Optimization

优化问题的常见示例包括在网络中查找最短路径、管理缓存、负载平衡、调度和计算机断层扫描(CAT扫描)。优化问题是计算机科学、工程学的许多分支、运筹学、生物信息学以及许多工业和经济环境中的基本问题。优化问题必须在非理想的条件下解决--当由于时间限制不可能有理想的解决方案时，或者因为关于问题实例的信息有限：例如，当解决方案必须随着时间的推移而逐步构建时，每一步都是在不知道未来约束的情况下进行的，或者当解决方案必须由许多代理构建时，每个代理都有自己的有限视图。这项研究开发了处理这种非理想条件的方法。一个直接的影响是，重要的优化问题可以在实践中得到更有效的解决。研究人员正在研究设施选址的变体、Qos网络中的缓冲区管理、可重构缓存、微处理器温度管理、网络拥塞控制、计算机层析成像以及线性和整数线性规划。研究人员还在为解决这类问题的算法建立统一的基础，并用将控制理论与最坏情况分析相结合的算法开辟新的天地。基础是概率方法、线性规划、原-对偶理论和控制理论。智力上的优点包括加深和统一对一类技术上令人敬畏的算法的理解。这反过来又会产生更广泛的影响，使算法更易于理解、教授和扩展。长期影响包括经济效率的提高以及技术的发展和传播。

Common examples of optimization problems include finding shortest routes in networks, managing caches, load balancing, scheduling, and computer tomography (CAT scanning). Optimization problems are fundamental to computer science, many branches of engineering, operations research, bioinformatics, and in many industrial and economic settings. Optimization problems must be solved in non-ideal conditions -- when ideal solutions are not possible due to time constraints, or because information about the problem instance is limited: for example, when the solution must be built in steps over time, with each step being taken without knowledge of future constraints, or when the solution must be built by many agents each with its own limited view. This research develops methods to deal with such non-ideal conditions. An immediate impact is that important optimization problems can be more effectively solved in practice.The researchers are studying variants of facility location, buffer management in QoS networks, reconfigurable caching, microprocessor temperature management, network congestion control, computer tomography, and linear and integer-linear programming. The researchers are also building a unifying foundation for algorithms for such problems, and breaking new ground with algorithms that integrate control theory with worst-case analysis. The foundations are in probabilistic methods, linear programming primal-dual theory and control theory. The intellectual merit includes deepening and unifying the understanding of a technically formidable class of algorithms. This in turn has the broader impact of making the algorithms easier to understand, teach, and extend. Long-term impacts include increased economic efficiency and development and dispersion of technology.