Gibt es einen schnellen Algorithmus für ein Problem mit minimalen Kostenrückkopplungen?

In einem gerichteten Graphen ist , , wenn eine DAG (gerichteter azyklischer Graph) ist, wird als Rückkopplungsbogenmenge bezeichnet. $G=(V,E)$ $F\subset E$ $G\setminus F$ $F$

Wenn jede Kante einem Gewicht , besteht das Problem des Rückkopplungsbogens für minimale Kosten darin, ein so zu finden, dass minimal ist. $w$ $F$ $W(F)$

Es ist bekannt, dass das Problem des minimalen Rückkopplungslichtbogensatzes NP-hart ist, ebenso wie das Problem des minimalen Rückkopplungslichtbogensatzes. Ich frage mich, ob jemand einen ungefähren Algorithmus kennt, der gut funktioniert, und Eigenschaften der Gewichtsfunktion, die einen schnellen Löser ergeben können.

ds.data-structures graph-theory np-hardness approximation-algorithms miao
quelle

Ich denke, Sie kennen Even, Naor, Schieber, Sudan (1998): "Annäherung an minimale Rückkopplungssätze und Mehrfachschnitte in gerichteten Graphen" - dx.doi.org/10.1007/PL00009191 ?

Jukka Suomela

Es gab mehrere unabhängige Entdeckungen von polylogarithmischen Näherungen für den allgemeinen Rückkopplungsbogensatz. Je nachdem, wonach Sie genau suchen, möchten Sie sich möglicherweise alle ansehen. Siehe die Papiere Leighton und Rao 1999; Seymour 1995; Sogar et al. 2000; Sogar et al. 1998 zitiert in meinem cs.brown.edu/~ws/papers/fast_journal.pdf .

Warren Schudy

Ich wollte nur klarstellen - ist dies richtig, dass nur das gerichtete Problem NP-schwer ist und das Problem für nicht gerichtete Graphen in Polynomzeit gelöst werden kann, siehe z. B. Diskussion über den Stapelüberlauf "So finden Sie die in einem ungerichteten Graphen festgelegte Rückkopplungskante". Ist das richtig, dass das Problem in Polynomzeit für ungerichtete Graphen gelöst werden kann?

TomR

@TomR Eine in einem ungerichteten Diagramm festgelegte Rückkopplungskante für das minimale Gewicht hat einen Spannbaum mit maximalem Gewicht als Ergänzung, den Sie in der Polytime finden können.

G. Bach

Vielleicht hilft das: arxiv.org/pdf/1702.07612.pdf

Prost

Antworten:

Daniel Apon hat auf die Konferenzversion meines Papiers verlinkt. Ich schlage stattdessen den Entwurf einer Journalversion vor: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
In Turniergraphen deuten einige experimentelle Arbeiten darauf hin, dass die lokale Suche recht gut funktioniert. Siehe das jüngste ALENEX-Papier von Anke van Zuylen und Frans Schalekampf: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
Wenn die Gewichte entweder "Wahrscheinlichkeitsbeschränkungen" oder "Dreiecksungleichungen" erfüllen, gibt es einen Konstantfaktor-Näherungsalgorithmus, der auf Quicksort basiert. Siehe Ailon, Charikar und Newmans jüngstes JACM-Papier.
Können Sie uns etwas mehr darüber erzählen, welche Art von Instanzen Sie im Sinn haben und ob Sie nach etwas suchen, das in der Praxis oder in der Theorie gut funktioniert?

Warren Schudy
quelle

Ihre Verbindung zu Zuylen und Schalekampf ist jetzt 404; informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans

nodakai

Siehe den Artikel "Wie man mit wenigen Fehlern rangiert: Ein PTAS für gewichtete Rückkopplungsbögen bei Turnieren" von Claire Kenyon-Mathieu und Warren Schudy (STOC 2007, Journalversion auf Schudys Seite), der ein Polynom-Zeit-Approximationsschema für die Sonderfall, bei dem der gerichtete Graph ein Turnier ist.

DS
quelle

Beide Papiere sind sehr interessant. Gibt es darüber hinaus einen submodularen funktionsbasierten Ansatz?

Miao

Bitte geben Sie Links.

Emil

@Emil, kopieren / Einfügen des Namens des Papiers in Google erhalten Sie beim ersten Treffer ein PDF: PDF .

Daniel Apon

Ich schlug lediglich einen Weg vor, die Antwort zu verbessern.

Emil