Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Primal-Dual Schema and Local Ratio
verfasst von : Ding-Zhu Du, Ker-I Ko, Xiaodong Hu
Erschienen in: Design and Analysis of Approximation Algorithms
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Based on the duality theory of linear programming, a new approximation technique, called the
primal-dual
schema, has been developed. With this technique, we do not need to compute the optimal solution of the relaxed linear program in order to get an approximate solution of the integer program. Thus, we can reduce the running time of many linear programming–based approximation algorithms from O(n3) to at most O(n2). Moreover, this method can actually be formulated in an equivalent form, called the
local ratio
method, which does not require the knowledge of the theory of linear programming. In this chapter, we study these two techniques and their relationship.