Discrete Mathematics and Optimization Seminar

---

Fabian Chudak
Swiss Federal Institute of Technology
Friday February 10th at 2.30pm
Burnside 934



Title. Solving large scale optimization problems.

Abstract. The focus of this talk is on the design of efficient algorithms capable of handling large scale
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 epsilon from the previously known
O(1/ epsilon^2) to O(1/ epsilon). In essence, the improvements are due to the fact that our algorithms
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.