City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Extended Formulations

Many optimization problems in Theoretical Computer Science can be transformed into linear (positive-semidefinite, etc.) optimization problems, where one identifies with each feasible solution of the optimization problem a point and where the objective function can be understood as a linear function over the constructed points. Such a transformation allows to obtain access to the machinery of linear programming. However, in many cases such linear programming formulation of the original optimization problem has large size. In the recent past, extended formulations attracted a lot of attention since they provide a potential way to reduce the size of these linear programming formulations.

Course Offerings

autumn 2019