Algorithms

Image courtesy of Prof. James Renegar

Algorithms are the engine at the core of the computerized solution of any mathematical model. For example, one might formulate some decision-making issue in terms of a linear program, but then how do you solve that linear program? With an algorithm. An algorithm can be analyzed theoretically and empirically; and this analysis might be focused on the quality of the solution found, or on how efficiently it is found. Whereas a theoretical analysis is typically a mathematical statement about the method, an empirical analysis of an algorithm typically involves its computer implementation, and the construction of benchmark data sets on which to evaluate the algorithm’s performance.

Faculty in the School of Operations Research and Information Engineering study a wide range of algorithmic questions. Although a large fraction of this work is on algorithms for optimization problems, this is only part of the algorithmic work being done at Cornell; among the topics studied are issues as diverse as finding the roots of a polynomial, computing economic equilibria (an issue important in a number of game-theoretic models), finding fair allocations of a resource, evaluating rankings for web pages, and even computing genetic maps (for a genome such as the tomato plant).

Faculty members have pioneered the design of algorithms in many of the core areas of mathematical programming; recent advances include interior-point algorithms for linear programming and semi-definite programming problems, as well as approximation algorithms for combinatorial optimization problems.

Algorithmic developments have included not only the pencil-and-paper work involved in proving results on the performance of algorithms, but have also encompassed the fruition of these ideas in publicly available software such as SDPT3 (for semi-definite programming) and the precursor of SYMPHONY (for integer programming). A recurring theme in the application areas for which algorithms are studied is the role of networks, such as in the design of cost-efficient networks or the routing of traffic in networks for their effective utilization. The fundamental role of algorithm design in solving problems is evident in the range of applications: inventory models, transportation models, and models with stochastic components.