Automating the Search for Small Hard Examples to Approximation Algorithms

Eklavya Sharma

Given an approximation algorithm $A$, we want to find the input with the worst approximation ratio, i.e., the input for which $A$'s output's objective value is the worst possible c…