Requirements for the Doctoral Program in ACO

Introduction

While Mathematics started out as an algorithmic science, mathematicians through the centuries have emphasized structural results rather than algorithmic or constructive ones. In recent years, however, because of both philosophical reasons and the advent of computers, there has been a renewed interest in the computational areas of mathematics. The branches of mathematics that deal with discrete structures, which we broadly classify as Combinatorics, are deriving particular benefit from this phenomenon. Traditionally, Combinatorics has been concerned with the existence, enumeration, and counting of discrete structures with certain properties; in the case of counting, for example, closed form or recurrence formulas were sought. The recent exploration of the computational aspects of Combinatorics has greatly contributed to the development of such areas as graph theory, matroid theory, and polyhedral theory, to name a few.

In the 40's and 50's, the field of Operations Research was born from the need to model real-world problems, other than those found in the natural sciences, in a systematic way, and put them into a mathematical form solvable by algorithms. Optimization under various constraints became the basic paradigm of quantitative methods for management, economics, and decision making in general. Linear and nonlinear programming emerged as new disciplines with pervasive applications. The simplex method proved to be a practical tool for solving large scale problems. Finally, the need for integer variables to deal with the discrete nature of the actions modeled or the indivisibility of the objects involved has led to the development of integer and combinatorial optimization, currently one of the most active research areas in applied mathematics. Examples of popular models in combinatorial optimization are network flows, including transportation and shortest path problems, matchings in graphs, set covering, and the traveling salesman problem.

The field of Computer Science was established in the 60's. In the 70's, computer scientists developed the striking theory of NP-completeness, which reduces to one another a whole range of computational problems from a myriad of areas, many of them dealing with discrete structures such as scheduling, number theory, logic, and graph theory. New research areas in the computational aspects of combinatorics were introduced, such as parallel algorithms and data structures.

In the last couple of decades, researchers in Mathematics, Operations Research, and Computer Science have made breakthroughs in developing polynomial time bounded algorithms for several important problems, including linear programming. In the case of the so-called NP-complete problems, substantial progress has been made in developing algorithms for approximate as well as exact solutions. Further, the probabilistic analysis of algorithms, where the efficiency of an algorithm is measured for an average instance, has been gaining ground. Interest in geometry has been revived through the study of its computational and combinatorial aspects. The geometry of numbers deals with the interplay between integer lattices and convex bodies; computational geometry addresses problems arising in robotics; and the geometry of integer polyhedra plays a central role in combinatorial optimization.

The mathematics used by computer scientists and operations researchers overlap to a large extent. The boundaries between Operations Research and Computer Science have become blurred. Important new theories and whole fields, like polyhedral combinatorics, have been and are being developed jointly by computer scientists, operations researchers, and applied mathematicians who consider themselves a little bit of both. Presentations of new results on graphs and matroid theory can be heard at Operations Research conferences, while papers on linear programming, network flows, and matchings in graphs are frequently presented at Computer Science conferences. The mathematical content of the papers has become greater and more diverse. Yet, in spite of this, few Ph.D students graduate with an equally solid knowledge of all three areas.

The Ph.D program in Algorithms, Combinatorics, and Optimization at Carnegie Mellon is intended to fill this gap. The program brings together the study of the mathematical structure of discrete objects and the design and analysis of algorithms in areas such as graph theory, combinatorial optimization, integer programming, polyhedral theory, computational algebra, geometry, and number theory.

Course Requirements and Research

Besides the core courses, a host of other courses are available for the students to take. Some examples are combinatorial optimization, graph coloring, matroid theory, convex polytopes, location theory, sequencing and scheduling, large scale OR, parallel algorithms, probabilistic analysis of algorithms, approximation algorithms, machine learning theory, cryptography, nonlinear programming, and optimal control theory. In the event that a student has already mastered a core course at the graduate level when entering the program, another course from the same department may be substituted. Approval must be obtained from the ACO Coordinating Committee and is given on a case-by-case basis. In addition, the students are expected to participate in the weekly research seminar on Algorithms, Combinatorics, and Optimization.

At the end of their third semester in residence, the students take a comprehensive qualifying examination based on the material in the above core courses. At this stage (or earlier), they choose a faculty member to supervise their research and dissertation. Approximately a year before the expected graduation date, the student must make a thesis proposal before a thesis committee, composed of the advisor and two or more faculty members of the student's choosing. The final transition point is the thesis defense, which is presented before the same committee. To graduate, the students will also need some teaching experience and must demonstrate adequate programming skill.

Questions about the ACO program can be addressed to any member of the ACO faculty.