Loading...
Please wait, while we are loading the content...
Similar Documents
On the equivalence between the primal-dual schema and the local ratio technique (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Rawitz, Dror Bar-Yehuda, Reuven |
| Description | In 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Number 2129 in Lecture Notes in Computer Science |
| Abstract | Abstract. We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm, and then transforming it into a primal-dual algorithm. This was done in the case of the 2-approximation algorithms for the feedback vertex set problem, and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [39]. In this paper we answer this question by showing that the two paradigms are equivalent. |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Primal-dual Algorithm Local Ratio Technique Approximation Paradigm Open Question Maximization Problem Feedback Vertex Local Ratio Algorithm First Primal-dual Algorithm Primal-dual Schema 2-approximation Algorithm Many Approximation Algorithm |
| Content Type | Text |
| Resource Type | Conference Proceedings |
