Diskussion:Approximationsalgorithmus

Die Unterscheidung in FPAS, PAS und Super-PAS läuchtet mir nicht ganz ein. Soweit ich es verstanden habe, kann ich da auch keinen Unterschied feststellen. Bei uns heißt das ganz allgemein immer PTAS. Je besser die Approximation (also je kleiner epsilon), desto höheren Grad n hat das Polynom mit n gegen unendlich für epsilon gegen null. Polynomial-Time bezieht sich immer auf die Länge. Wie soll es sich auf ein fest gewähltes epsilon beziehen? --Coma 15:49, 30. Jul 2003 (CEST)

Optimierungproblem

Ich habe, nachdem ich die alten Änderungen durchgesehen habe, meine Ergenzung "Optimierungsproblem" zurückgenommen. Wenn man von Approximationsalgorithmen spricht, meint man aber im Allgemeinen die Approximation von Optimierungsproblemen.

Ergebnisse aus dem Review

Ich werde den Artikel im Laufe des Monats entstehen lassen, noch ist nichts zu sehen - über Hilfe freue ich mich immer. --Ixitixel 09:13, 1. Mär 2006 (CET)

"über Hilfe freue ich mich immer" - gerne - worum geht's? /me peilt gar nüscht von dem bisherigen Artikel ;O) -- Achim Raschka 09:20, 1. Mär 2006 (CET)

Fallen darunter eigentlich nicht auch Algorithmen für nicht exakt lösbare Probleme? Ich denke da gerade an die Hartree-Fock-Methode und würd mich freuen, wenn Du mir den dazu passenden Algorithmus erklärst =) --Taxman ^議論 11:12, 1. Mär 2006 (CET)

Ich muß gestehen ich habe gerade das erste mal von der Hartree-Fock-Methode Methode gehört - mit Physik habe ich auch icht s am Hut. Die Frage nach "Algorithmen für nicht exakt lösbare Probleme" ist schon spannender. Im Artikel zur Methode steht nur das das Problem analytisch nicht lösbar ist da bieten sich numerische Verfahren natürlich an - wichtig um einen Approximationsalgorithmus beschreiben zu können ist aber das die Performanz des Algorithmus bestimmbar ist. Das heißt es muß zumindest überprüfbar sein ob eine Lösung optimal ist - ich will mich aber gerade noch nicht so weit aus dem Fenster lehnen. Primär will ich auch den Unken arbeiten, aber am Wochenende schreibe ich mal los, und vielleicht kann ich Deine Frage ja dann mit erledigen. --Ixitixel 11:23, 1. Mär 2006 (CET)

Deine neue Definition ist falsch. Ein Approximationsalgorithmus ist erstmal ein Algorithmus, der die Loesung eines mathematischen Problems approximiert. --DaTroll 14:20, 14. Mär 2006 (CET)

Hmm Schöning definiert den Approximationsalgorithmus erstmal nur für Optimierungsprobleme. --Ixitixel 14:36, 14. Mär 2006 (CET)

Das mag ja sein, dass das in der theoretischen Informatik so gemacht wird. Es hat ja auch eine gewisse Berechtigung, weil man immer argumentieren kann, dass man die Norm des Fehlers von Naeherung zu exakter Loesung minimieren will. Diese Motivation sollte man aber schon darlegen (wobei mir dann nicht klar ist, wieso man sich ueberhaupt auf Optimierungsprobleme beschraenkt), darueberhinaus gibt es genug Probleme, wo die exakte Loesung einfach nicht bekannt ist. Auch dann kann man manchmal noch Aussagen ueber den Abstand zur exakten Loesung machen, die Bezeichnung Optimierungsproblem ist dann aber wirklich nur noch kuenstlich. In anderen Worten: Ein Approximationsalgorithmus loest ein Approximationsproblem, eben die Definition die vor Deiner Ueberarbeitung noch im Artikel stand. --DaTroll 14:51, 14. Mär 2006 (CET)

Nennen Mathematiker Näherungsverfahren und Algorithmen für Approximationsprobleme und solches Zeug denn auch Approximationsalgorithmus? Ich denke das wären dann zwei grundsätzlich unterschiedliche Dinge, die man dann auch in unterschiedlichen Artikel behandeln sollten (auch wenn man die möglicherweise irgendwie künstlich zusammenbringen kann). In der Informatik ist ein Approximationsalg. immer ein Alg. der eine approximative Lösung für ein Optimierungsproblem liefert. Dabei existiert für das Optimierungsproblem immer auch ein Alg. der eine exakte Lösung findet. Allerdings ist der oft zu langsam (expontiell, polynomiell mit hohem grad, linear mit großem Vorfaktor), weshalb man sich oft mit Lösungen begnügt, die in einem gewissen Sinn nur wenig schlechter als eine optimale Lösung sind. --Koethnig 15:16, 28. Mär 2006 (CEST)

Ich hab's jetzt im Einleitungssatz ergänzt - werde es morgen weiter überarbeiten. Danke für den hinweis. --Ixitixel 15:07, 14. Mär 2006 (CET)

So richtig erkenne ich nicht worauf der Artikel eigentlich hinausläuft, obwohl ich mich beruflich mal mit Nichtlinearer Regression und Approximationen beschäftigt und sogar mal ein Gauss-Jordan-Verfahren programmiert habe. Die Einleitung ist bereits sehr fachchinesisch, vielleicht erstmal Annäherung (Approximation) verwenden, also das deutsche Wort zuerst. Dann sollte in die Einleitung wo und wofür man das braucht, wer gleich auf Optimierungsproblem klicken muss, kommt wahrscheinlich nicht zurück ;-). --Uwe G. ¿⇔? 03:42, 15. Mär 2006 (CET)

1. mir fehlt da ein beispiel, ein wirklich netter kleiner approx für ein allgemein bekanntes problem mit wertetabelle oder grafik, damit man dem algo bei der arbeit zuschauen kann. gib auch beispiele: nullstellensuche, numerische differentiation, und such stuff, auch weblinks, aber in der WP gibt's da sicher was, verlinken, da haben wir sicher schon 20 artikel drüber.
2. /*Güte von Approximationsalgorithmen*/ beschreibt die a-posteriori-abschätzung, die in den allermeisten fällen nutzlos ist, weil wir v* ja nicht kennen. schreib was über a-priori-abschätzung, die braucht man wirklich

--W!B: 10:44, 21. Mär 2006 (CET)

begriffsprobleme

approximationsguete

der begriff "approximationsguete" ist mir schon haeufig untergekommen; teilweise auch "performance", aber "performanz" habe ich in diesem kontext noch nicht gelesen. ich schlage vor, den gelaeufigeren(?) und verstaendlicheren begriff "approximationsguete" im artikel zu verwenden und stelle zudem die frage nach der relevanz des begriffes "performanz". -- 141.3.74.36 19:18, 19. Okt. 2006 (CEST)

Der Begriff ist mir auch nie untergekommen, aber sowieso ist die Symbolik hier sehr willkuerlich gewaehlt worden und auch wenn mir Alles formal sehr korrekt vorkommt, wuerde ich persoenlich Vieles in standardisierte Form ummuenzen. OPT, I, II, evtl. waer ein leichtes Beispiel auch ganz hilfreich. --Schwarzer8Kater 19:24, 18. Feb. 2008 (CET)

Obwohl man das natürlich so verwenden kann, macht die Performanz das Lesen hier nicht einfacher. Das was hier als Performanz bezeichnet wird, heißt sonst einfach Approximationsgüte, und ist dann eben definiert in Abhängigkeit davon, ob es sich um ein Minimierungs- oder Maximierungsproblem handelt. Dadurch ist die Approximationsgüte immer größer gleich 1, und man wird die Performanz los. --141.3.26.222 11:40, 6. Mär. 2009 (CET)

Effizienz/Effektivität

Im Artikel ist zweimal die Rede von "effektiver Lösbarkeit" die Rede, z.B: "Die Abkürzung APX steht für approximable und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effektiv approxmierbar(sic!) ist." Auch auf der APX-Unterscheidungsseite steht "Klasse der effektiv approximierbaren Probleme in der Informatik; siehe Approximationsalgorithmus". Es geht hier um Effizienz im Sinne polynomialer Lösbarkeit. Das hat mit Effektivität nichts zu tun. Ich schlage vor alle Vorkommnisse von "effektiv" durch "effizient" zu ersetzen. --141.3.26.222 11:40, 6. Mär. 2009 (CET)

Approximationsgüte

Üblicherweise nimmt man hier das max und nicht das min bei der Bildung der Approxg., was dann Güten >=1 zur Folge hat. Sicherlich könnte man das auch so wie im Artikel definieren, es ist bloß halt nicht gängig.

Kann mich da nur anschließen. Die Definition der Güte ist natürlich Geschmacksfrage, aber in den relevanten Veröffentlichungen (z.B. Feige, Lund, Lovasz, Safra, Goldwasser, ...) werden Güten >=1 verwendet. Das ist insbesondere bei Problemen mit höchstens logarithmischer oder polynomieller Güte einfach griffiger. - Graui

Kann mich dem nur anschliessen, hatte das Min zunaechst uebersehen und deswegen schon fast reflexartig das >=1 eingesetzt.. wuerde das aber sowieso nach Fallunterscheidung behandeln: "Falls II Minimierungsproblem/Falls II Maximierungsproblem". Denke dadurch blickt der Laie auch etwas mehr durch warum das so gemacht wird und wo das Ganze herkommt. :-) --Schwarzer8Kater 11:31, 19. Feb. 2008 (CET)

Polynomialer Algorithmus

Was ist ein polynomialer Algorithmus? --Abdull 20:56, 15. Jun. 2008 (CEST)

Ein Algorithmus, der in polynomieller Zeit von einer deterministischen Turingmaschine gelöst wird, bspw O(1), O(n), O(log n), O(n^k) für festes k usw, im Gegensatz zu exponentieller Laufzeit o.ä. (nicht signierter Beitrag von 80.135.231.145 (Diskussion) 11:33, 28. Aug. 2010 (CEST))

Approximationsklassen

Was in dem Artikel steht (nämlich PTAS, FPTAS und APX), ist weder vollständig noch sortiert. Es gibt 5 Approximationsklassen: NPO-1 (aka PTAS), NPO-2 (aka FPTAS), NPO-3 (aka APX), NPO-4 (aka f(n)-APX) und NPO-5, die über die Schwellsprache an die Klassen P, NP gekoppelt sind; siehe Algorithmics for Hard Problems von Hromkovic. Aber bevor ich der Wikipedia noch Irrelevanz hinzufüge, lasse ich meine genauere Ausführung lieber sein. Wer es genau wissen will, lese in besagter Quelle oder woanders weiter. (nicht signierter Beitrag von 80.135.231.145 (Diskussion) 11:33, 28. Aug. 2010 (CEST))

Unverständlich

Die Güte gibt doch Auskunft über ein Verhältnis/Qualität aus. Deshalb verstehe ich auch nicht warum der Wert(v=value) der Lösung, als Güte bezeichnet wird. Alternativ wird auch v* als v_opt bezeichnet(Wegener, Komplexitätstheorie).--95.91.62.194 10:54, 11. Jun. 2012 (CEST)