Konvexe Volumenapproximation - Convex volume approximation

In der Analyse von Algorithmen haben mehrere Autoren die Berechnung des Volumens von hochdimensionalen konvexen Körpern untersucht , ein Problem, mit dem auch viele andere Probleme der kombinatorischen Aufzählung modelliert werden können . Häufig verwenden diese Arbeiten ein Black-Box-Berechnungsmodell, bei dem die Eingabe durch eine Subroutine zum Testen, ob ein Punkt innerhalb oder außerhalb des konvexen Körpers liegt, gegeben wird, anstatt durch eine explizite Auflistung der Scheitelpunkte oder Flächen eines konvexen Polytops . Es ist bekannt, dass in diesem Modell kein deterministischer Algorithmus eine genaue Approximation erreichen kann, und selbst für eine explizite Auflistung von Flächen oder Vertices ist das Problem #P-hard . Eine gemeinsame Arbeit von Martin Dyer , Alan M. Frieze und Ravindran Kannan lieferte jedoch ein randomisiertes polynomiales Zeit-Approximationsschema für das Problem, das einen scharfen Kontrast zwischen den Fähigkeiten von randomisierten und deterministischen Algorithmen liefert.

Das Hauptergebnis des Papiers ist eine randomisierte Algorithmus zum Auffinden einer Annäherung an das Volumen eines konvexen Körpers in -dimensionalen euklidischen Raum durch die Existenz einer Mitgliedschaft unter der Annahme , Oracle . Der Algorithmus benötigt Zeit begrenzt durch ein Polynom in , die Dimension von und . Der Algorithmus kombiniert zwei Ideen: ${\displaystyle\varepsilon}$${\displaystyle K}$${\displaystyle n}$${\displaystyle n}$${\displaystyle K}$${\displaystyle 1/\varepsilon}$

• Durch die Verwendung eines Markov-Chain-Monte-Carlo- (MCMC)-Verfahrens ist es möglich, Punkte zu erzeugen, die innerhalb eines gegebenen konvexen Körpers nahezu gleichmäßig zufällig verteilt sind. Das Grundschema des Algorithmus ist eine nahezu gleichmäßige Abtastung von innen, indem ein Gitter aus -dimensionalen Würfeln platziert und ein zufälliger Spaziergang über diese Würfel durchgeführt wird. Mit der Theorie der sich schnell mischenden Markov-Ketten zeigen sie, dass es eine polynomielle Zeit braucht, bis sich der Random Walk auf eine nahezu gleichmäßige Verteilung eingependelt hat.${\displaystyle K}$${\displaystyle n}$
• Durch die Verwendung von Rejection Sampling ist es möglich, die Volumina von zwei konvexen Körpern zu vergleichen, die ineinander verschachtelt sind, wenn ihre Volumina innerhalb eines kleinen Faktors voneinander liegen. Die Grundidee besteht darin, zufällige Punkte innerhalb des äußeren der beiden Körper zu erzeugen und zu zählen, wie oft diese Punkte auch innerhalb des inneren Körpers liegen.

Der gegebene konvexe Körper kann durch eine Folge von verschachtelten Körpern angenähert werden, die schließlich einen mit bekanntem Volumen (eine Hypersphäre) erreichen, wobei dieser Ansatz verwendet wird, um den Faktor zu schätzen, um den sich das Volumen bei jedem Schritt dieser Folge ändert. Die Multiplikation dieser Faktoren ergibt das ungefähre Volumen des ursprünglichen Körpers.

Dieses Werk brachte seinen Autoren 1991 den Fulkerson-Preis ein .

Verbesserungen

Obwohl die Zeit für diesen Algorithmus polynomiell ist, hat er einen hohen Exponenten. Nachfolgende Autoren verbesserten die Laufzeit dieser Methode, indem sie für das gleiche Problem schneller mischende Markov-Ketten zur Verfügung stellten.

Verallgemeinerungen

Das Ergebnis der Polynomialzeit-Approximabilität wurde auf komplexere Strukturen wie die Vereinigung und den Schnitt von Objekten verallgemeinert. Dies hängt mit dem Maßproblem von Klee zusammen .

Verweise