Antoulas, A. C.; Zhu, B.; Zhang, Q.; York, B.; O'Malley, B. W.; Dacso, C. C.: A novel mathematical method for disclosing oscillations in gene transcription: A comparative study. PLoS ONE 13 (9), e0198503 (2018)
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.
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.
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
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).
Global Optimization of Unconventional Formulations for Sustainable Energy Systems