Wir möchten wissen, ob es bekannte Approximationsergebnisse für den kardinalitätsbeschränkten minimalen - - Schnitt in gerichteten Graphen gibt. Ein solches Ergebnis konnten wir in der Literatur nicht finden.
Das Problem ist wie folgt definiert:
Instanz: Ein gerichteter Graph , eine Kostenfunktion , zwei Eckpunkte und eine ganze Zahl .w : E → R + 0 s , t ∈ V k
Lösung: Ein - t - Schnitt, dh eine Aufteilung von V in zwei Mengen V 1 , V 2, so dass s ∈ V 1 , t ∈ V 2 und die Anzahl der Kanten, die den Schnitt kreuzen, höchstens k , dh | ist { ( u , v ) ∈ E : u ∈ V 1 , v ∈ V 2 } | ≤ k .
Maßnahme (zu minimieren): Die Kosten des Schnitts:
In " Cardinality Constrained and Multicriteria (Multi) Cut Problems " beweisen die Autoren, dass dieses Problem selbst für ungerichtete Graphen stark NP-schwer ist.
Wir sind hauptsächlich an Approximationsalgorithmen für gerichtete Graphen interessiert, aber auch Approximationsergebnisse für den ungerichteten Fall könnten nützlich sein.
Vielen Dank für alle Einblicke.
Antworten:
Wir können eine Bi-Kriterien-Näherung wie folgt erhalten (oder allgemeiner ( 1 + ε , 1 + 1 / ε ) Bi-Kriterien-Näherung).( 2 , 2 ) ( 1 + ε , 1 + 1 / ε )
Wir können davon ausgehen, dass wir die Kosten der optimalen Lösung kennen. Bezeichnen wir es durch . Sei w ' ( u , v ) = w ( u , v )O P.T.
Betrachten Sie die optimale Lösung(V1,V2). Dann ist
∑(u,v)∈E( V 1 , V 2 )w'(u,v)=∑(u,v)∈E( V 1 , V 2 )(w(u,v)
quelle