Talk:Approximation algorithm

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Computer science Start‑class High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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

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)[reply]

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 ρ. —Preceding unsigned comment added by C. lorenz (talk • contribs) 18:23, 24 April 2009 (UTC)[reply]