Conferences > ORSSA 2019 > Tutorial

48th ORSSA Annual Conference (2019)

Optional Pre-conference Tutorial

Introduction to the Design of Approximation Algorithms

Nearly all of the relevant problems, that we need to solve day after day in production, logistics, project management and (supply chain) scheduling, etc., cannot be solved to optimality in a reasonable (available) amount of time. Heuristics, local search, nature inspired methods, beam search, etc. are the way of obtaining good solutions that are not provably near optimal. The algorithms performance is generally evaluated in a comprehensive computational study or simulation which justify a users confidence that the methods will satisfactorily solve her problems in practice. Approximation algorithms are solution methods where the quality of the result can be estimated (e.g. in the worst case) or the optimal value can be even approximated arbitrarily close.

This tutorial will give an introduction into the design of approximation algorithms. Some of the more common techniques will be described and illustrated by a number of examples. In order to follow the course some basic knowledge of Operations Research or Combinatorial Optimization is sufficient.

A good introductory book is David P. Williamso, David B. Shmoys, 2011. The Design of Approximation Algorithms, Cambridge University Press.

Date and time The tutorial will take place from 14:00 to 17:00 on Sunday 8 September.

Price The cost of the tutorial will be R500 per person. The cost covers the hire of a separate venue and refreshments during the tea break (lunch not included).

About the presenter

Prof. Erwin Pesch

Erwin Pesch, University of Siegen, Germany and Center for Advanced Studies in Management, HHL Leipzig, Germany, studied Mathematics and Computer Science at the Technical University Darmstadt. He was employed as a Software Engineer and a research assistant at the Commerzbank AG and the business institute of the Technical University Darmstadt, respectively. He worked as an assistant professor at the Faculty of Economics and Business Administration of the University in Maastricht (Netherlands) from 1989 to 1994 and as a full professor at the Institute of Economics of the University in Bonn from 1994 to 2001. Currently, he is a full professor at the Faculty of Economics and Business Administration of the University in Siegen and director of the Center for Advanced Studies in Management (CASiM) at the HHL Leipzig Graduate School of Management.

He holds a Ph.D. in Mathematics and a Habilitation in Business Administration both from the Technical University Darmstadt. His research areas are in Logistics, Decision Support, Project Management, Personnel Planning and Scheduling many of which are closely related to different industry projects.

He is author or co-author of 7 books and has published about 200 papers in many international journals, among others in Management Science, Mathematical Programming, Transportation Science, INFORMS Journal on Computing, Networks, Artificial Intelligence, Journal of Combinatorial Theory, Journal of Graph Theory, Discrete Mathematics, Discrete Applied Mathematics, European Journal of Operational Research, Journal of Scheduling, Naval Research Logistics, IEEE Transactions on Robotics and Automation, Annals of Operations Research, etc.

He is area editor of INFORMS Journal on Computing, Omega, and Annals of OR, as well as member of another 10 editorial boards, has frequently been a keynote or plenary speaker at international conferences, and was responsible for the organization of the ECCO 2001 and the EURO 2009 conference in Bonn that attracted 2500 delegates.

He obtained a number of scientific awards, among them the

  • the *Science Award of the German Operations Research Society (GOR) in 2017,
  • the *Copernicus Prize* from the Germany National Science Foundation (DFG) in 2012,
  • the *Minister Award of the Polish Minister for Research and Education in 2008,
  • and has been ranked among the 0,5 - 1% leading positions in all citation and publication based rankings in Germany, Austria and Switzerland since 2005
Page last modified on February 24, 2019, at 01:41 PM