Speaker: Jon Lee, IBM Watson Research Center

Title: Parametric Nonlinear Discrete Optimization

Abstract: I will discuss polynomial-time algorithms for solving problems of the form max { f(Wx) : x in F }, where f is a nonlinear function, the rows of the matrix W can be thought of as describing several linear objectives, and F is a discrete set of feasible solutions. The nonlinear function f can be thought of as balancing the various linear objectives. We look at various combinatorial choices of F. So our work can be seen to fit somewhere on the landscape between multi-criteria optimization and nonlinear combinatorial optimization.

In the most general setting, the model is intractable, so we look at cases that yield polynomial-time algorithms and approximation schemes. Our specific results involve broad special cases. E.g., regarding F, we consider multi-knapsacks, matchings, matroids and polymatroids. Regarding f, we consider minimization of concave and convex functions, generalization of norms, etc. Regarding W, to get positive results, we usually need to assume that it has a fixed number of rows and the entries are small in some sense.

Most of our algorithms were mainly designed for theoretical efficiency. Nonetheless, there is a good argument for trying to implement some of these methods on modern high-performance platforms. We describe such a successful effort, using ultra-high precision solution of linear systems on the BlueGene supercomputer.

All of this is joint work, different parts with Berstein, Gunnels, Margulies, Maruri-Aguilar, Onn, Riccomagno, Weismantel, Wynn.

Place: Science and Technology Building I, Room 242

Refreshments will be served before the talk at 3:00 p.m. in Room 222.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491