Viele praktische Optimierungsprobleme sind NP-schwer. Aus diesen Grund kann fur diese Probleme mit der Annahme N ist ungleich NP kein Algorithmus konstruiert werden, der in Polynomialzeit eine optimale Losung bestimmt. Jedoch werden in der Praxis nicht immer optimale Losungen benotigt und es reicht meistens schon eine Naherungslosung aus. Approximationsalgorithmen konnen eine solche Naherungslosung bestimmen. Sie zeichnen sich durch ihre polynomiale Laufzeit aus und haben eine konstante Gutegarantie. Aus diesen Grund eignen sich Approximationsalgorithmen fur die Berechnung von Losungen fur Facility Location und k-Median Problemen. Hierbei handelt es sich um NP-schwere Optimierungsprobleme, die vielfaltige Anwendungsmoglichkeiten in der Praxis besitzen.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.