Friday February 10th at 2.30pm

optimization problems. Our main interests are in the seemingly disjoint areas of convex optimization

and combinatorial optimization. Most practical combinatorial optimization problems are inherently hard

to solve. In contrast, their convex relaxations can be solved efficiently. Very often these fractional

(or relaxed) solutions not only provide very good bounds, but also reveal nontrivial information about

the combinatorial structure of good solutions to the original problems. Thus the connection between the

two areas is transparent.

After motivating the topic, I will concentrate on our main results that concern linear programming

relaxations of combinatorial optimization problems. Specifically we present a generic paradigm

for the design of improved approximation schemes to solve these relaxations. For instance, for

the case of the uncapacitated facility location problem we will show an algorithm that substantially

improves the running time dependence on the relative error

are gradient-based as opposed to the previously known subgradient-based algorithms. We will also present

some very preliminary computational experiments that indicate that our approach could be very competitive

in practice. Our results build mainly on work of Nesterov and some of them extend the work of Bienstock

and Iyengar. This work is partially joint with my student Vania Eleuterio.

Finally I will briefly elaborate on current research including an application of non-smooth convex

optimization to portfolio optimization.