ABSTRACT
For many practically important optimization problems, no efficient algorithms for solving them exactly or even in an approximate way are known, and, relying on the standard complexity-theoretic assumptions such as P ≠ N P https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_11715.tif"/> , it is likely that this situation will never change. In a classical optimization problem, a set of instances is given and an algorithm is considered successful if it computes an exact solution or a solution with a pre-specified approximation guarantee for each of these instances without any additional prior knowledge. This viewpoint might be overly pessimistic as, in many situations, some additional knowledge is available that is not incorporated into the modeled optimization problem. A common thread of modern algorithmics is to identify such additional information and to make good use of it.
