Vorlage: Standardbild

MALOC Event Series

3439 1446721298

Magdeburg Lectures on Optimization and Control: No Small Linear Program Approximates Vertex Cover within a Factor 2-ε

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor 2-ε, assuming Khot's famous Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor 2-ε has super-polynomially many inequalities. [mehr]

MALOC Event Series

3889 1452171036

Magdeburg Lectures on Optimization and Control: "Concepts of Function Space Oriented Optimization"

Many large scale nonlinear optimization problems are discretizations of optimization problems in function space and thus, we expect that additional functional analytic structure should be present. The goal of function space oriented optimization is to exploit this structure. This may comprise the efficient computation of steps by iterative solvers, problem suited globalization strategies, or the use of adaptive mesh refinement inside an optimization method. In this talk we will give an overview of a couple of ideas, and explain at concrete examples how they can be implemented. Short CV Anton Shiela is a professor for applied mathematics at the University of Bayreuth. His fields of research are optimization with PDEs, in particular the development of algorithms for the solution of optimization problems in function space. Before moving to Bayreuth in 2014, he was an associate professor at Technische Universitaet Hamburg-Harburg (2013-2014) and Matheon junior reseach group leader at TU Berlin (2012-2013). He got his PhD in 2007 at Zuse Institute Berlin, where he worked as a reasearch assistant (2002-2012). [mehr]

loading content