Approximation Algorithms for Combinatorial Optimization

University Of California-Riverside, Riverside CA

Investigators

Abstract

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.