Näherungsalgorithmen für Probleme in P

Man denkt normalerweise darüber nach, Lösungen (mit Garantien) für NP-harte Probleme zu approximieren. Gibt es Forschungsarbeiten zur Approximation von Problemen, von denen bereits bekannt ist, dass sie in P vorkommen? Dies könnte aus mehreren Gründen eine gute Idee sein. Ein Näherungsalgorithmus, der nicht so gut zu verstehen ist, kann mit einer viel geringeren Komplexität (oder sogar einer viel kleineren Konstante) ausgeführt werden, weniger Platz beanspruchen oder besser parallelisierbar sein.

Schemata, die Zeit- / Genauigkeits-Kompromisse ermöglichen (FPTAS und PTAS), könnten auch für Probleme in P mit niedrigeren Grenzen, die bei großen Eingaben nicht akzeptabel sind, sehr attraktiv sein.

Drei Fragen: Fehlt mir etwas, das dies offensichtlich zu einer schlechten Idee macht? Wird an der Entwicklung einer Theorie dieser Algorithmen geforscht? Wenn nicht, kennt jemand einzelne Beispiele für solche Algorithmen?

Wie Jukka hervorhebt, ist die rechnerische Geometrie eine reiche Quelle von Problemen, die in der Polynomzeit gelöst werden können, aber wir möchten schnelle Näherungen erhalten. Das klassische "ideale" Ergebnis ist ein "LTAS" (lineares Zeitnäherungsschema), dessen Laufzeit die Form - üblicherweise werden diese durch Extrahieren einer Konstanten erhalten Kernel mit einer Größe von (Poly ( )) aus den Daten und Ausführen eines teuren Algorithmus auf diesem Kernel mit der Garantie, dass eine genaue Lösung auf dem Kernel eine ungefähre Lösung für die gesamte Eingabe ist.1 /$O(n + \text{poly}(1/\epsilon))$$1/\epsilon$

Es gibt eine Reihe von Tricks, Reduzierungen und Prinzipien, und das neue Buch von Sariel Har-Peled ist voll davon. Ich glaube nicht, dass es eine umfassende Komplexitätstheorie als solche gibt.

$P$

$\mathcal{O}(n\cdot\text{polylog}(n))$

(Liste der Artikel) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html

$\epsilon$

$s-t$

3) Finden einer spärlichen Näherung der Fourier-Transformation eines Signals in der sublinearen Zeit http://arxiv.org/pdf/1201.2501v1.pdf

4) Ermitteln der ungefähren Hauptkomponente einer Matrix http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf

Mir ist keine allgemeine Theorie bekannt, die sich mit Approximationsalgorithmen für Probleme in P befasst. Ich kenne jedoch ein bestimmtes Problem, das als ungefähre Distanz-Orakel bezeichnet wird:

$G = (V, E)$$n = |V|$$m = |E|$$s, t \in V$

$1$$O(1)$$O(m + n\log n)$

$k$

Für spärliche Graphen kann ein allgemeinerer Kompromiss zwischen Raum-Annäherung-Zeit gezeigt werden .

Wir suchen häufig nach Näherungslösungen für einfache Probleme wie das Auffinden des kürzesten Pfades in einem Diagramm und die Ermittlung der Anzahl eindeutiger Elemente in einer Menge. Die Einschränkung hier ist, dass die Eingabe groß ist und wir das Problem ungefähr mit einem einzigen Durchlauf über die Daten lösen möchten. Es gibt verschiedene "Streaming" -Algorithmen, mit denen sich ungefähre Lösungen in linearer / nahezu linearer Zeit erzielen lassen.

$O(nm)$$n$$m$

Schnelle Approximationsalgorithmen für maximale Übereinstimmung sind bekannt. Mindestens einer, der mir sofort einfällt, ist http://arxiv.org/pdf/1112.0790v1.pdf .

$P$

Ich denke, dass der gesamte Bereich des Datenstroms und der sublinearen Algorithmen eine Anstrengung in diese Richtung ist. Beim Daten-Streaming liegt der Schwerpunkt auf der Lösung der Probleme im o (n) - und idealerweise im O (polylog (n)) -Raum, während bei sublinearen Algorithmen versucht wird, Algorithmen mit einer Laufzeit von o (n) zu erhalten. In beiden Fällen muss man oft Kompromisse eingehen, wenn man einen randomisierten Approximationsalgorithmus hat.

Sie können mit dem Material auf dieser Seite und diesem beginnen .

$\epsilon$$\epsilon$. Es gibt eine Reihe von Artikeln zur Lösung spezieller Fälle von linearen Programmierproblemen wie Multicommodity-Flows (und allgemeiner zum Packen und Abdecken von LPs). Es gibt keine separate Näherungstheorie für Probleme in P gegenüber Problemen in NP (wir wissen nicht, ob P gleich NP ist oder nicht). Man kann über eine bestimmte Technik sprechen, die für eine bestimmte Klasse von Problemen anwendbar ist. Beispielsweise sind allgemeine Techniken zum ungefähren Lösen von Packungen und zum Abdecken von linearen Programmen und einige Varianten bekannt.

Dimitris erwähnt die Approximation von Fouriertransformationen. Dies wird in großem Umfang bei der Bildkomprimierung verwendet, z. B. im JPEG-Algorithmus. [1] Obwohl ich noch keine Veröffentlichung gesehen habe, die dies betont, scheint es, dass eine verlustbehaftete Komprimierung [2] (mit ableitbaren Grenzen) auch als P-Zeit-Approximationsalgorithmus verwendet werden kann. Die Approximationsaspekte sind in dem Sinne hochentwickelt und fein abgestimmt / spezialisiert, dass sie so optimiert sind, dass sie vom menschlichen Sehen nicht wahrgenommen werden können, dh die menschliche Wahrnehmung von Kodierungsartefakten (grob definiert als Unterschied zwischen Approximation und verlustfreier Komprimierung) wird minimiert.

Dies hängt mit Theorien darüber zusammen, wie das menschliche Auge die Farbcodierung über einen algorithmischen Prozess "annähert" oder tatsächlich wahrnimmt. Mit anderen Worten, das theoretische Näherungsschema / der theoretische Näherungsalgorithmus ist tatsächlich absichtlich so konzipiert, dass er mit dem physikalischen / biologischen Näherungsschema / -algorithmus (der durch biologische Informationsverarbeitung, dh Neuronen im menschlichen visuellen System, kodiert wird) übereinstimmt.

Die Kompression ist also eng mit der Approximation gekoppelt. In JPEG wird die Fouriertransformation durch die diskrete DCT-Cosinustransformation angenähert [3]. Ähnliche Prinzipien werden für den MPEG-Videokomprimierungsstandard für mehrere Frames angewendet. [4]

[1] JPEG-Komprimierung, Wikipedia

[2] verlustbehaftete Komprimierung, Wikipedia

[3] DCT, diskrete Cosinustransformation, Wikipedia

[4] MPEG, Wikipedia

Vielleicht ist dies nicht genau die Antwort auf Ihre Frage, denn momentan kann ich mich nur an einige Heuristiken erinnern, aber ich bin mir sicher, dass es einige Annäherungen gibt, da ich sie zuvor gesehen habe.

$O(f(k)*|G|^\alpha)$$f(k)$ Problem und seine späteren Annäherungen / Heuristiken (einfache Google zeigt Ergebnisse in 2010, 2011) oder Algorithmen zum Auffinden der Baumzerlegung von Graphen.

http://www.sciencedirect.com/science/article/pii/S0020019002003939

ist ein Link zum Artikel "Ein einfacher Näherungsalgorithmus für das Problem des gewichteten Abgleichs" von Doratha Drake und Stefan Hougardy, der das Problem des gewichteten Abgleichs behandelt.