In the 9^th century, the Persian mathematician and astronomer Muhammad ibn Musa al-Khwarizmi devised a detailed set of rules on how to solve linear and quadratic equations. Three hundred years later, his set of rules, as well as his name, were translated into Latin in the work “Algoritmi de numero Indorum” – “Algoritmi on the numbers of Indians”. Over the centuries to follow, his name developed into the word we know today: the ‘algorithm’ was born.

Algorithms are everywhere

But what are algorithms? They seem to be everywhere: YouTubers complain that the company’s algorithm is costing them views, sophisticated algorithms are threatening to take away human jobs, and Cambridge Analytica’s algorithm enabled the Trump presidency as well as Brexit.

While there are many different definitions of ‘algorithm’, they all agree on this: an algorithm is a set of well-defined instructions to solve a class of problems.

Mushroom risotto

We all work with algorithms every day. My roommate’s mushroom risotto recipe that she was kind enough to write down for me is an algorithm. It’s well-defined because I asked her to be specific enough so that not even I could mess it up. It solves a class of problems: not having mushroom risotto. This is a whole class of problems because it doesn’t just solve the problem for me on a rainy Sunday afternoon, but for anyone at any time, as long as they have access to a stove, two pots, risotto rice, mushrooms, onions, garlic, olive oil, butter, salt and pepper, parmesan, and a reasonably priced white wine.

Three different types

Using algorithms to solve mathematical optimization problems, we differentiate between three types: exact algorithms, approximation algorithms, and heuristics.

Exact algorithms return the optimal solution every time, they are the gold standard, the holy grail. But, as I and many others have learned, math is hard. Some problems take ages to solve, and exact algorithms run on and on and would take years, in some instances millions of years to return a solution. For these types of problems, approximation algorithms and heuristics come to the rescue. Both return solutions that are probably not optimal. But, at least for approximation algorithms, we know an upper bound for how far from optimal the returned solution is, while for heuristics we do not.

Throw it into the pot

If I knew that making mushroom risotto without the parmesan would make a risotto that is at least half as good as the authentic version, this modified recipe would be an approximation algorithm. If, however, I were to just throw the contents of my kitchen cupboard willy-nilly into a pot, pour some reasonably priced white wine over it and decide to call it a risotto, I would have no idea how tasty – or even edible – the result would be. This would be a heuristic.

Outperforming the best-known approximation

In practice, however, there are many cases where a well-designed heuristic outperforms the best-known approximation algorithm. One example is the so-called Vertex Cover Problem, a classic optimization problem in computer science and graph theory. The best fast approximation algorithm for this problem has a so-called ‘guarantee’ of 2, meaning that the returned solution can be almost twice as bad as the optimum, so not very good at all. Meanwhile, some heuristics regularly beat this algorithm, getting close to, or even achieving, optimal solutions. So, while they may get a bad rap because of the inherent risk of poor performance, heuristics are vital when solving complex problems.

Roast mammoth

Muhammad ibn Musa al-Khwarizmi isn’t just the namesake for ‘algorithm’. His name is also the origin of the Spanish word for ‘digit’ and he is also the founder of algebra. While this is certainly an impressive resumé, he is most certainly not the first person to develop an algorithm. That honor probably goes to some cave person who explained to a friend how to make excellent roast mammoth in such detail that not even they could mess it up.

Want to learn more about OMP optimization?