Optimale Greedy-Algorithmen für NP-harte Probleme

38

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.

Shiva Kintali
quelle
Suresh (oder) Ryan, können Sie bitte einen Tag mit dem Namen "hardness-of-approximation" hinzufügen und diese Frage mit einem Tag versehen. Ich kann mit meinem aktuellen Ruf keine neuen Tags hinzufügen :( Da auch lange Tags (> 20 Zeichen) nicht zulässig sind, sollte es
vermutlich
Hallo Shiva, ich habe das Härte-von-ungefähr-Tag hinzugefügt, wie Sie vorgeschlagen haben, aber ich persönlich denke, dass die Annäherungshärte besser klingt und möglich sein sollte, da sie kürzer als die Annäherungsalgorithmen ist.
Kaveh
6
Schön gewählter erster Satz. ;)
AlcubierreDrive

Antworten:

19

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,,nxi1/21/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 P7/8P=NP

Ryan Williams
quelle
16

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.

gphilip
quelle
1
ist der maximale Matching-Algorithmus wirklich gierig?
Suresh Venkat
Ja, da es bei jedem Schritt eine lokal optimale Wahl trifft. Der Algorithmus trifft tatsächlich eine lokale / machbare / Wahl, aber da die Kanten ungewichtet sind, ist dies auch eine optimale Wahl.
Gphilip
11

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.
Jagadisch
quelle
11

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.

Ashwinkumar BV
quelle
1
Die Nemhauser-Wolsey-Fisher-Analyse des Greedy-Algorithmus ist nur für den Fall der Maximierung unter einer einfachen Kardinalitätsbeschränkung. Gierig gibt es auch für die einfache Partition Matroid nur eine -Anäherung. Die -Angleichung zur Maximierung einer submodularen Funktion, die einer willkürlichen Matroide unterliegt, ist ein aktuelles Ergebnis, das Vondrak und anderen (einschließlich mir) zu verdanken ist. Es basiert auf mehreren Tools und ist kein gieriger Algorithmus. ( 1 - 1 / e )1/2(11/e)
Chandra Chekuri
Natürlich, mein Fehler. Die Antwort wurde bearbeitet, um die Korrektur widerzuspiegeln.
Ashwinkumar BV
10

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

Lev Reyzin
quelle
Ich denke, dies ist das gleiche Problem wie die Antwort von @ AshwinkumarBV, die ich vermutlich geschrieben habe, während ich meine
eingetippt habe
6

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 .kG=(V,E)dij0i,jVk

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.kSV,|S|=kkkkrr

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 | = kiVS|S|<kjVd(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 22kρρ<2P=NPkk2-Näherung wird von Hochbaum und Shmoys gegeben, Eine bestmögliche Heuristik für das k-Zentrum-Problem, 1985 .

Juho
quelle
5

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|Cmax

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

Oleksandr Bondarenko
quelle
1

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

Nikos M.
quelle