Optimale Greedy-Algorithmen für NP-harte Probleme

Gier ist, mangels eines besseren Wortes, gut. Eines der ersten algorithmischen Paradigmen, die im Einführungskurs zu Algorithmen vermittelt werden, ist der gierige Ansatz . Gieriger Ansatz führt zu einfachen und intuitiven Algorithmen für viele Probleme in P. Interessanterweise führt der offensichtliche und natürliche gierige / lokale Algorithmus bei einigen NP-harten Problemen zu einem (nachweislich) optimalen Approximationsfaktor (unter geeigneten komplexitätstheoretischen Annahmen). Ein klassisches Beispiel ist das Set Cover Problem . Ein natürlicher Greedy-Algorithmus liefert einen Näherungsfaktor von O (ln n), der optimal ist, es sei denn, P = NP.

Nennen Sie einige natürliche gierige / lokale Algorithmen für NP-harte Probleme, die unter geeigneten komplexitätstheoretischen Annahmen nachweislich optimal sind.

Die Methode der bedingten Erwartungen (zur Derandomisierung der "Random Assignment" -Algorithmen für Max-Cut und Max-SAT) kann als gierige Strategie angesehen werden: Für wählen Sie den Wert einer Variablen wie z dass die erwartete Anzahl der in der resultierenden reduzierten Instanz erfüllten Bedingungen die erwartete Anzahl der in der aktuellen Instanz erfüllten Bedingungen überschreitet. (Tatsächlich ist der gierige Algorithmus zur -Anpassung von Max-Cut derselbe wie der Algorithmus zur "Methode der bedingten Erwartungen" zur -Anpassung von Max-Cut.)$i=1,\ldots,n$$x_i$$1/2$$1/2$

Da die Methode auch für Max-E3-SAT funktioniert und eine Annäherung erreicht, ist dies ein Beispiel für einen Greedy-Algorithmus, der eine optimale Annäherung darstellt, es sei denn, (vgl. Hastad- und Moshkovitz-Raz-Unannäherungsergebnisse für Max- E3-SAT).P = N $7/8$$P=NP$

Vertex Cover: Der beste Algorithmus zur Approximation konstanter Faktoren besteht darin, (gierig) eine maximale Übereinstimmung zu finden und alle beteiligten Vertices als ungefähre Lösung auszuwählen. Dies ergibt eine 2-Approximationslösung, und eine bessere Approximation mit konstanten Faktoren ist nur möglich, wenn die Unique Games Conjecture falsch ist.

Subhash Khot und Oded Regev, Vertex-Abdeckung ist möglicherweise schwer auf 2-ε , JCSS 74 (3), 2008 anzunähern.

Off Topic: Ich denke, das ist ein wirklich netter Näherungsalgorithmus, zumal er im Nachhinein so trivial ist.

Finden Sie in einem gerichteten Graphen den azyklischen Teilgraphen mit der maximalen Anzahl von Kanten.

Trivialer 2-Approximationsalgorithmus: Wählen Sie eine beliebige Reihenfolge der Eckpunkte und nehmen Sie entweder die vorderen oder hinteren Kanten.

Es ist bekannt, dass es schwierig ist, die 2-Approximation zu schlagen (obwohl es möglicherweise nicht NP-schwer ist).

• Die zufällige Reihenfolge zu übertreffen ist schwierig: Unangemessenheit der maximalen azyklischen Subgraphen Venkatesan Guruswami, Rajsekar Manokaran und Prasad Raghavendra.

Die submodulare Maximierung in Bezug auf die Kardinalitätsbeschränkung hat eine 1: 1 / e-Gier-Approximation. Der Algorithmus stammt von Nemhauser, Wolsey, Fisher. Die NP-Härte ergibt sich aus der np-Härte der eingestellten Abdeckung, da die maximale Abdeckung ein Sonderfall der submodularen Maximierung ist.

Greedy gibt eine (1-1 / e) -Näherung an die Max-k-Abdeckung, und dies kann nicht verbessert werden, es sei denn, P = NP.

Finden eines Mindestgrades MST. Es ist nicht schwer, da es ein Sonderfall ist, einen Hamilton-Pfad zu finden. Ein lokaler Suchalgorithmus gibt innerhalb einer additiven Konstante 1 an.

Referenz

Annäherung des Steiner-Baums mit minimalem Grad an einen optimalen Wert

Das Zentrum-Problem ist ein Clustering-Problem, bei dem wir einen vollständigen ungerichteten Graphen mit einem Abstand zwischen jedem Knotenpaar . Die Abstände entsprechen der Dreiecksungleichheit und der Modellähnlichkeit. Wir erhalten auch eine ganze Zahl .$k$$G = (V,E)$$d_{ij} \geq 0$$i,j \in V$$k$

In dem Problem müssen wir Cluster finden, die die Scheitelpunkte, die am ähnlichsten sind, zu Clustern zusammenfassen. Wir wählen eine Menge von Clusterzentren. Jeder Scheitelpunkt ordnet sich dem nächstgelegenen Clusterzentrum zu und gruppiert die Scheitelpunkte in verschiedene Cluster. Ziel ist es, den maximalen Abstand eines Scheitelpunkts zu seinem Clusterzentrum zu minimieren. Wir wollen also geometrisch die Zentren von verschiedenen Kugeln mit dem gleichen Radius , die alle Punkte abdecken, damit so klein wie möglich ist.$k$$S \subseteq V, |S| = k$$k$$k$$k$$r$$r$

Der optimale Algorithmus ist gierig und auch sehr einfach und intuitiv. Wir wählen zuerst einen Scheitelpunkt willkürlich aus und setzen ihn in unsere Menge von Cluster-Zentren. Wir wählen dann das nächste Clusterzentrum so aus, dass es so weit wie möglich von allen anderen Clusterzentren entfernt ist. Also während , so finden wir immer wieder eine Ecke für die der Abstand maximiert wird und es hinzuzufügen . Einmal wir sind fertigS | S | < K j ∈ V d ( j , S ) S | S | = $i \in V$$S$$|S| < k$$j \in V$$d(j,S)$$S$$|S| = k$

Der beschriebene Algorithmus ist ein Approximationsalgorithmus für das Zentrumsproblem. In der Tat, wenn es existiert ein -Approximationsalgorithmus für das Problem mit dann . Dies kann leicht mit einer Reduktion des NP-vollständigen Dominanzmengenproblems gezeigt werden, indem gezeigt wird, dass wir eine dominante Menge von Größen höchstens wenn eine Instanz des Zentrumsproblems, in der alle Abstände entweder 1 oder 2 sind, einen optimalen Wert hat 1. Der Algorithmus und die Analyse werden von Gonzales, Clustering, 1985, zur Minimierung der maximalen Entfernung zwischen den Clustern angegeben . Eine andere Variante einerk ρ ρ < 2 P = N P k k $2$$k$$\rho$$\rho < 2$$P = NP$$k$$k$$2$-Näherung wird von Hochbaum und Shmoys gegeben, Eine bestmögliche Heuristik für das k-Zentrum-Problem, 1985 .

Das Listenplanungsverfahren von Graham ist optimal für die prioritätsbeschränkte Planung auf identischen Maschinen sei denn, eine neue Variante der einzigartigen Spielvermutung von Bansal und Khot ist falsch.$P|prec|C_{max}$

Bedingte Härte der Präzedenzzeitplanung auf identischen Maschinen von Ola Svensson

Vielleicht würde Sie das auch interessieren (angepasst von Methoden zur Übersetzung globaler Einschränkungen in lokale Einschränkungen )

Da gierige Methoden (genauer gesagt lokale Methoden) nur lokale Informationen verwenden, um eine globale Optimierung zu erreichen, bietet sich eine (global) optimale Lösung für Probleme an, wenn Wege gefunden werden, die globale Bedingungen in Bedingungen umwandeln, die nur mit lokalen Informationen verwendet werden können nur mit gierigen / lokalen Techniken.

Verweise:

1. Global denken, lokal fit sein: unbeaufsichtigtes Lernen niedrigdimensionaler Mannigfaltigkeiten (Journal of Machine Learning Research 4 (2003))
2. Globale Optimierung unter Verwendung lokaler Informationen mit Anwendungen zur Flusskontrolle, Bartal, Y.
3. Warum natürlicher Farbverlauf ?, Amari S., Douglas SC
4. Lokale Optimierung globaler Ziele: Wettbewerbsfähige verteilte Deadlock-Lösung und Ressourcenzuteilung, Awerbuch, Baruch, Azar, Y.
5. Lernen mit lokaler und globaler Konsequenz
6. Bedingungszufriedenheitsprobleme, die durch lokale Konsistenzmethoden gelöst werden können

Es gibt einige Referenzen, die sich mit dem Problem der Übertragung globaler Bewertungsfunktionen (oder Einschränkungen) auf lokale Funktionen (unter Verwendung lokaler Informationen) und ihrer Konsistenz (dh Konvergenz auf dasselbe globale Optimum) befassen:

1. Lokale Auswertungsfunktionen und globale Auswertungsfunktionen für Computational Evolution, HAN Jing, 2003
2. Entstehung der lokalen Bewertungsfunktion, Han Jing und Cai Qingsheng, 2002

Abstract (von 1. oben)

Dieser Aufsatz präsentiert einen neuen Blick auf die rechnerische Evolution unter dem Gesichtspunkt der Lokalität und Globalität von Bewertungsfunktionen zur Lösung des klassischen kombinatorischen Problems: das kcoloring-Problem (Entscheidungsproblem) und das Minimum Coloring-Problem (Optimierungsproblem). Wir überprüfen zunächst die aktuellen Algorithmen und modellieren das Farbproblem als Multiagentensystem. Wir zeigen dann, dass der wesentliche Unterschied zwischen herkömmlichen Algorithmen (Local Search, wie zum Beispiel Simulated Annealing) und verteilten Algorithmen (wie zum Beispiel dem Alife & VRE-Modell) in der Bewertungsfunktion liegt: Simulated Annealing verwendet globale Informationen, um den gesamten Systemstatus zu bewerten, der aufgerufen wird die Methode der Global Evaluation Function (GEF); Das Alife & VRE-Modell verwendet lokale Informationen, um den Status eines einzelnen Agenten zu bewerten. Dies wird als LEF-Methode (Local Evaluation Function) bezeichnet. Wir vergleichen die Leistung von LEF- und GEF-Methoden zur Lösung der k-Farbprobleme und der minimalen Farbprobleme. Die Computer-Versuchsergebnisse zeigen, dass der LEF mit GEF-Methoden (Simulated Annealing and Greedy) vergleichbar ist. In vielen Problemfällen schlägt der LEF GEF-Methoden. Gleichzeitig analysieren wir die Beziehung zwischen GEF und LEF: Konsistenz und Inkonsistenz. Der Konsistenzsatz zeigt, dass die Nash-Gleichgewichte eines LEF mit den lokalen Optima eines GEF identisch sind, wenn der LEF mit dem GEF konsistent ist. Dieser Satz erklärt teilweise, warum der LEF das System zu einem globalen Ziel führen kann. Einige Regeln für die Erstellung eines konsistenten LEF werden vorgeschlagen. Neben der Konsistenz

Specificaly die Papiere Adressen Methoden determnine , ob eine lokale Funktion (LEF) ist konsistent mit einer globalen Funktion (GEF) und Verfahren konsistent LEF aus gegebener GEFs (zu konstruieren Consistency Theorem ).

Auszug aus dem Fazit (von 1. oben)

Dieses Papier ist nur der Anfang von LEF & GEF-Studien. Neben dem obigen Forschungsbericht gibt es noch viel zu tun: Weitere Experimente zu LEF-Methoden; analytische Studie zu LEF; ausreichende lokale Informationen für LEF; und die Existenz einer konsistenten GEF für jeden LEF; Ist das Konsistenzkonzept ausreichend? Können wir LEF & GEF auf genetische Algorithmen anwenden, da genetische Algorithmen auch eine Bewertungsfunktion (Fitnessfunktion) haben? … Es ist unsere Absicht, all diese Fragen zu untersuchen und zu beantworten