L-reduction

L-reduction

L-reduction is a transformation of optimization problems which keeps the approximability features. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems.

The term "L reduction" is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept.

Definition

Let A and B be optimization problems and cA and cB their respective cost functions. A pair of functions R and S is an L-reduction if all of the following conditions are met:
* functions R and S are computable in logarithmic amount of space,
* if x is an instance of problem A, then R(x) is an instance of problem B,
* if y is a solution to R(x), then S(y) is a solution to x,
* there exists such positive constant α that:OPT(R(x)) le alpha OPT(x)
* there exists such positive constant β that:|OPT(x)-c_A(S(y))| le eta |OPT(R(x))-c_B(y)|

Properties

It can be shown that if (R,S) is an L-reduction of problem A to B with constants α and β (see above) and there exists a polynomial ε-approximation algorithm for B then there also exists a polynomial δ-approximation algorithm for A where:delta = alphaetaepsilonThis also implies that if B has a polynomial-time approximation scheme then so does A.

ee also

* Approximation algorithm,
* NP-complete,
* MAXSNP.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • réduction — [ redyksjɔ̃ ] n. f. • fin XIIIe « rapprochement »; lat. reductio, de reducere → réduire I ♦ (XIVe) Opération qui consiste à remettre en place (un os luxé, fracturé; un organe déplacé). Réduction d une articulation luxée. Par ext. Réduction d une… …   Encyclopédie Universelle

  • Reduction — Reduction, reduced, or reduce may refer to:cienceChemistry*Reduction – chemical reaction in which atoms have their oxidation number (oxidation state) changed. **Reduced gas – a gas with a low oxidation number **Ore reduction: see… …   Wikipedia

  • Reduction d'endomorphisme — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Réduction d'endomorphismes — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Réduction des endomorphismes — Réduction d endomorphisme En mathématiques, et plus particulièrement en algèbre linéaire, la réduction d endomorphisme est une technique mathématique qui a pour objectif d exprimer des matrices et des endomorphismes sous une forme plus simple,… …   Wikipédia en Français

  • Reduction potential — (also known as redox potential, oxidation / reduction potential, ORP or Eh) is a measure of the tendency of a chemical species to acquire electrons and thereby be reduced. Reduction potential is measured in volts (V), or millivolts (mV). Each… …   Wikipedia

  • Reduction d'ISF pour investissement en PME — Réduction d ISF pour investissement en PME L article 16 de la loi TEPA du 21 août 2007 a créé une réduction d ISF en cas d investissement dans les PME non cotées. La réduction est de 75% des sommes investies. Elle est plafonnée à 50 000 €.… …   Wikipédia en Français

  • Réduction d'isf pour investissement en pme — L article 16 de la loi TEPA du 21 août 2007 a créé une réduction d ISF en cas d investissement dans les PME non cotées. La réduction est de 75% des sommes investies. Elle est plafonnée à 50 000 €. Sommaire 1 L investissement en direct 2 Rappels… …   Wikipédia en Français

  • reduction — re‧duc‧tion [rɪˈdʌkʆn] noun FINANCE 1. [countable, uncountable] when prices, costs etc become lower or are made lower: • Our winter sale includes many price reductions. • We can make a reduction (= sell something more cheaply …   Financial and business terms

  • Reduction des risques lies a la toxicomanie — Réduction des risques liés à la toxicomanie La réduction des risques liés à la toxicomanie désigne l ensemble de la politique de réduction des risques lié à la toxicomanie. C est une politique qui privilégie des stratégies de soin et de… …   Wikipédia en Français

  • Reduction (philosophy) — Reduction is the process by which one object, property, concept, theory, etc., is shown to be explicable in terms of another, higher level, concept, object, property, etc. For example, we say that chemical properties such as the boiling point of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”