Approximation Algorithms and Hardness of Approximations
Bundit Laekhanukit , PhD Student, McGill

Area: Discrete Math

Abstract:

Optimization problems are problems that naturally arise in many computational tasks. For example, consider a situation in which we want to route a packet between two nodes in a network; then this problem can be phrased as the shortest path problem, which is a well-studied optimization problem. Unfortunately, while we can solve the shortest path problem in polynomial time, many other optimization problems are NP-hard, which means that we could not expect a polynomial-time algorithm that could solve the problems optimally unless P = NP. Hence, we turn to algorithms that find approximate solutions in (quasi) polynomial-time, giving birth to the area of approximation algorithms. In this talk, we will discuss how to design approximation algorithms for NP-hard problems, and we will discuss that some problems have high approximation resistance, i.e., it is NP-hard even to find a good approximate solution.