HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE

Department of Computer Science Colloquium
2015 Series

How to Improve Measuring of the Hardness of NP-hard Optimization Problems

Prof. Juraj Hromkovic
Department of Computer Science
ETH Zurich

Date: March 16, 2015 (Monday)
Time: 4:30 - 5:30 pm
Venue: WLB210, Wing Lung Bank Building, Shaw Campus

Abstract
The NP-hardness was introduced as a concept for classifying problems with respect to the amount of computational work necessary and sufficient to solve them. But this classification is very rough because it is based on the worst-case-measurement and so few hard problem instances make the problem hard. Here we present our concept of stability of approximation for discrete optimization problems that enables to partition the set of all problem instances into an infinitely many sets of instances with respect to their hardness. The hardness is measured as the ability to get efficiently a solution that is a good approximation of the optimal solutions.

Biography
Juraj Hromkovic has been Full Professor of Information Technology and Education at the Department of Computer Science at ETH Zurich since January 2004. Born in Bratislava in 1958, study of computer science at the Comenius University, 1986 PhD, 1989 habilitation, 1990-1994 visiting professor at the University of Paderborn, 1994-1997 professor for parallel computing at Christian Albrechts University Kiel, 1997-2003 professor for algorithmics and complexity at RWTH Aachen. In 2001 elected as the member of the Slovak Academic Society and in 2010 elected as the member of the European Academy. He is a full professor at ETH Zurich since 2004. His research and teaching interests focus on informatics education, algorithmics for hard problems, and complexity theory with special emphasis on the relationship between determinism, randomness and non-determinism. One of his main activities is writing textbooks which make complex recent discoveries and methods accessible for students and practitioners and so contributing to the speed up of the transformation of new paradigmic research results into educational folklore.

********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)

http://www.comp.hkbu.edu.hk/v1/?page=seminars&id=327&lang=sc
Photos