Este site utiliza cookies para lhe proporcionar uma melhor experiência de utilização. Ao navegar aceita a política de cookies.

"ALGO Talks" with Arne Herzel

23 abril
ALGO Talks
ALGO Talks

On 23 April, Arne Herzel, who is currently finishing his PhD thesis on "Approximation Methods for Multiobjective and Parametric Optimization Problems" at the University of Kaiserslautern, will give a talk entitled "One-exact ε-Pareto sets".


Password: 638245

"ALGO talks" is a seminar series organized by the ALGorithms and Optimization Lab, Adaptive Computation Group, CISUC and University of Coimbra.

Abstract: For multiobjective optimization problems, an ε-Pareto set is a set of feasible solutions that, for each (efficient) solution, contains a solution that dominates it up to a factor of 1+ε. It is well known that the polynomial-time solvability of a certain single-objective problem determines the class of multiobjective optimization problems that admit a polynomial-time computable ε-Pareto set. Similarly, in this talk, we characterize the class of problems having a polynomial-time computable ε-Pareto set that optimizes one objective function exactly by the efficient solvability of an appropriate single-objective problem. This class includes important problems such as multiobjective shortest path and spanning tree and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective problems from this class, we provide an adaptive algorithm that computes a one-exact ε-Pareto set of cardinality at most twice the cardinality of a smallest such set.

Bio: Arne Herzel is currently finishing his PhD thesis on Approximation Methods for Multiobjective and Parametric Optimization Problems at the University of Kaiserslautern, Germany. During his bachelors and masters studies, also at the University of Kaiserslautern, he specialized in combinatorial optimization and game theory. He also studied at the University of Auckland, New Zealand, for one semester abroad, where his focus was on simulation methods and statistics.