Talk:Approximation algorithm: Difference between revisions

There was an error on this page, specifically that the "dominance number" is made to sound as if it is a "replacement" for some other measure, whereas the reference I found calls it an orthoganal measure. There should probably still be a section about other measurements of approx. algorithms. The paper [1] I found that confirmed this error had some interesting contetnt that perhaps someone should write up. --NotQuiteEXPComplete 16:50, 22 August 2006 (UTC)

An obvious problem: R_a is used to define R_a; whassup? Gritzko 06:30, 11 June 2007 (UTC)

One is a function, the other is a set. You are right though, it'd probably be less confusing to use another variable.--NotQuiteEXPComplete 09:26, 20 June 2007 (UTC)

References for Approximation Guarantees

Seeing how there are many different and varying definitions used for approximation guarantees, I would preferably like to see inline sources. The article currently uses ρ-approximation algorithms (relative performance guarantee) and I strongly believe that the definition is taken from Handbook of Approximation Algorithms and Metaheuristics but I cannot verify this myself. The definition used also agrees with "factor δ approximation algorithms" from Vazirani's book but it does not agree with the usual performance ratio which in Cormen et.al. uses the symbol ρ.