Approximationsalgorithmen für gerichteten Mindestschnitt mit Kardinalitätsbeschränkungen

8

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.st

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 kG=(V,E)w:ER0+s,tVk

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 .stVV1,V2sV1tV2k|{(u,v)E:uV1,vV2}|k

Maßnahme (zu minimieren): Die Kosten des Schnitts:

(u,v)E:uV1,vV2w(u,v)

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.

Steven
quelle
Entschuldigung, es ist keine Antwort. Eigentlich möchte ich fragen, wie die Bi-Kriterien-Näherung in die Monokriterien-Näherung übertragen werden kann. bitte verzeih mir.
Jianhao Ma

Antworten:

11

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 )OPT 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)

w(u,v)=w(u,v)OPT+1k.
(V1,V2)
(u,v)E.(V.1,V.2)w'(u,v)=(u,v)E.(V.1,V.2)(w(u,v)ÖP.T.+1k)=1+|E.(V.1,V.2)|k2.

st(V.1',V.2')Gw'2(V.1',V.2')

E.(V.1',V.2')=(u,v)E.(V.1',V.2')1k(u,v)E.(V.1',V.2')w'(u,v)2k
(u,v)E.(V.1',V.2')w(u,v)ÖP.T.(u,v)E.(V.1',V.2')w'(u,v)2ÖP.T..
Yury
quelle
Vielen Dank. Ihr Algorithmus ist sehr interessant und aufschlussreich. Leider scheint es, dass ein Bicriteria-Approximationsalgorithmus für uns nicht ausreicht, da wir jede ungefähre Lösung benötigen, um unter Berücksichtigung der Kardinalitätsbeschränkung durchführbar zu sein. Wissen Sie, ob ein solches Ergebnis in der Literatur bekannt ist? Danke noch einmal!
Steven
k(k+1)/.2V.=s,t,xsx(k+1)/.2xtk+1(k+1)/.2xe=2/.(k+1)sxxe=1- -2/.(k+1)xt1(k+1)/.2.
Yury
(k+1)/.2