Preface

The American Mathematical Society sponsors a series of Short Courses, each

of which consists of a set of survey lectures on a single theme of pure and applied

mathematics. Initiated in 1973, these two-day courses occur immediately preced-

ing the Joint Mathematics Meetings held in January as well as at some summer

meetings.

On January 5-6, 2004, the AMS Short Course Trends in Optimization 2004 took

place in Phoenix, Arizona. Optimization has not been the focus of a recent AMS

Short Course. Past Short Courses on related themes consist of: (i) Operations

Research, Washington D.C., 1975, (ii) Applied Combinatorics, Kalamazoo, 1975,

and (iii) Operations Research, Duluth, 1979. There have been impressive advances

in optimization since then, and our goal was to showcase some of the exciting more

recent work.

Our Short Course consisted of seven 75-minute lectures given by leaders in the

field of optimization. It is impossible to give a thorough cross-section of research

in optimization in a two-day course. Rather, we chose seven exciting areas to focus

on, with a clear bias toward the discrete side of optimization, somewhat reflecting

the interests of the organizers. This volume comprises edited notes prepared by our

lecturers.

Optimization is concerned with the efficient computation of the supremum of

an objective function f whose domain is restricted to some set of feasible solutions

S. Assumptions about the function / (linear, convex, continuous, differentiable,

etc.) and the set S (a hypercube, a convex set, a polyhedron, the integer lattice

points in a polyhedron, the set of symmetric positive semidefinite matrices, etc.)

lead to structural results and/or efficient algorithms. When the set S is a subset of

the power set of a finite set, we are in the domain of combinatorial optimization.

No sophisticated background is needed in order to read the lecture notes in

this volume. Many of them are self-contained and all provide extensive references.

However, basic knowledge of linear programming duality (which appears in almost

all chapters), the geometric combinatorics of polyhedral sets (extreme points and

rays, faces, valid inequalities, etc.), and the geometry of integer programming would

be useful. There are many nice books devoted to each topic above, but most cover

more than the introductory material. A good starting point where the reader

can find the needed material in a condensed but very readable form is Chapter 0

of Jon Lee's textbook A First Course in Combinatorial Optimization (Cambridge

University Press, 2004).

Karen Aardal (Georgia Institute of Technology) in her lecture Lattice basis

reduction in optimization, describes Lovasz's fundamental algorithm for producing

a short vector in a lattice by lattice basis reduction, and H.W. Lenstra's use (in the

vii