Session 1C: Inaugural Lectures by Fellows/Associates

Coping With (np) Hardness

The vast majority of optimization problems arising in practical applications are NP-hard. Thus, it is difficult to overstate the importance of understanding how to handle NP-hard problems algorithmically. When a problem is NP-hard, this means that (unless P = NP) there cannot exist an algorithm that solves all instances of the problem optimally using time polynomial in the size of the instance. However, this does not mean that algorithmists stand powerless in the face of NP-hardness. Speaker’s research focuses on designing algorithms that are meant to cope with NP-hardness.