Random Solutions Are Often Good Enough

There is a subfield of computer science known as approximation algorithms whose goal is to find algorithms that can quickly find solutions that are not necessarily optimal, but are within some known bound of optimal. Under very reasonable assumptions, the expected value for the constant of approximation of a randomly selected feasible solution is almost always going to at most two. We present some empirical evidence suggesting that the random solutions are often even closer to optimal than ones produced by state-of-the-art approximation algorithms. Sometimes quickly and mindlessly choosing a random solution isn’t half bad!