Le 03/11/2007 par liberti :

14/1/2008 at 10:30, LIX, Ecole Polytechnique (Salle des Seminaires)

NONLINEAR COMBINATORIAL OPTIMIZATION

Jon Lee
IBM T.J.Watson research center, Yorktown Heights, NY, USA

We present an algorithmic framework for solving problems of the form

max c x + f(W x),
s.t. x in F

The rows of W can be thought of as several linear objectives. The
nonlinear function f can be though of as balancing these objectives
against a primary objective funtion c. We look at various
combinatorial settings for the choices of F So this can be seen to fit
somewhere on the landscape between multicriteria optimization and
nonlinear discrete optimization. Our specific results are
polynomial-time algorithms for broad special cases (e.g.,
multi-knapsack, matroids, polymatroids), given very specific
hypotheses on the presentation of c and W. There is an interesting
application to model-fitting/experimental-design.

This is joint work with Shmuel Onn (Technion) and Robert Weismantel
(Magdeberg).