Event Details
On Approximability of NP-hard Optimization Problems
Presenter: Dr. Venkatesh Srinivasan - Postdoctoral Researcher, Max Planck Institute for Informatik (MPI), Germany
Supervisor: Dr. Frank Ruskey, Professor, Computer Science Department
Date: Thu, April 24, 2003
Time: 13:30:00 - 14:30:00
Place: Engineering Office Wing Building (EOW), Room # 430
ABSTRACT
ABSTRACT:
Many optimization problems of theoretical and practical interest are known to be NP-hard. Unless P=NP, there are no polynomial time algorithms that give optimal solutions for these problems. Hence, it is natural to ask if we can design efficient algorithms that give reasonably good solutions on all instances. An algorithm is said to be a C-approximation algorithm if, on all instances, it produces a solution whose cost is within a factor C of the optimum. The theory of approximability of NP-hard optimization problems has been an active area of research in the past decade.
In this talk, I will survey some of the basic techniques used in designing approximation algorithms and proving hardness of approximation results. I will then describe my recent results in this area by focusing on the following NP-hard optimization problem.
Given a set of points in a high-dimensional Euclidean space, the goal is to output the best lower-dimensional subspace that describes this set of points.
Note: Dr. Srinivasan is a candidate for a Tier II Canada Research Chair in Foundations of Computer Science