Pi Day 2022 Talk - Limits of Approximability, Magic Numbers in Scheduling

Pi Day 2022 Talk - Limits of Approximability, Magic Numbers in Scheduling

In the study of algorithms, we desire provably-correct algorithms that efficiently solve problems. In this talk, the area of approximation algorithms is introduced in the context of determining the existence of efficient algorithms for hard optimization problems. If P is not equal to NP, which is one possibility for the outstanding and fundamental P vs.

NP problem, then for some intractable problems there may only exist polynomial-time algorithms that can compute approximately close answers to optimal solutions, but no better than multiplicatively by some “magic number”.

The talk will briefly introduce a mixture of algorithms, computational complexity theory, and recent developments focusing on intractable problems intersecting scheduling and graph theory.