Mostnaturaloptimizationproblems,includingthosearisinginimportant
applicationareas,areNP-hard.Therefore,underthewidelybelievedconjecture
thatP-=/=NP,theirexactsolutionisprohibitivelytimeconsuming.
Chartingthelandscapeofapproximabilityoftheseproblems,viapolynomial
t
