Algoritma pendekatan untuk Cut Minimum yang Diarahkan dengan Kendala Kardinalitas

Kami ingin tahu apakah ada hasil perkiraan yang diketahui untuk kardinalitas minimum - - potong pada grafik yang diarahkan. Kami tidak dapat menemukan hasil seperti itu dalam literatur. $s$ $t$

Masalahnya didefinisikan sebagai berikut:

Instance: Grafik berarah , fungsi biaya , dua simpul dan integer . $G=(V,E)$ $w : E \to \mathbb{R_0^+}$ $s,t \in V$ $k$

Solusi: Sebuah - -cut, yaitu partisi dari menjadi dua set sehingga , dan jumlah tepi yang melintasi dipotong adalah paling , yaitu . $s$ $t$ $V$ $V_1, V_2$ $s \in V_1$ $t \in V_2$ $k$ $|\{ (u,v) \in E: u \in V_1, v \in V_2 \}| \le k$

Ukur (untuk meminimalkan): Biaya pemotongan:

\sum_{(kamu, v) \in E : kamu \in V_{1}, v \in V_{2}} w (kamu, v)

$\sum_{ (u,v) \in E : u \in V_1, v \in V_2 } w(u,v)$

Dalam " Cardinality constrained dan multicriteria (multi) cut issues" autor membuktikan bahwa masalah ini sangat NP-Hard bahkan untuk grafik yang tidak diarahkan.

Kami terutama tertarik pada algoritme aproksimasi untuk grafik berarah, tetapi hasil aproksimasi untuk case yang tidak diarahkan mungkin juga berguna.

Terima kasih atas wawasannya.

ds.algorithms graph-theory co.combinatorics graph-algorithms approximation-algorithms Steven
sumber

Maaf itu bukan jawaban, sebenarnya saya ingin bertanya bagaimana cara mentransfer perkiraan bi-kriteria ke perkiraan mono-kriteria? tolong maafkan saya.

Jianhao Ma

Kita bisa mendapatkan perkiraan dua kriteria sebagai berikut (atau lebih umum perkiraan dua kriteria). $(2,2)$ $(1+\varepsilon, 1 + 1/\varepsilon)$

Kami dapat berasumsi bahwa kami tahu biaya solusi yang optimal. Nyatakan dengan . Biarkan Pertimbangkan solusi optimal . Kemudian $OPT$

w^{'} (kamu, v) = \frac{w (kamu, v)}{HAI P T} + \frac{1}{k} .

$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$

(V_{1}, V_{2})

$(V_1, V_2)$

\sum_{(kamu, v) \in E (V_{1}, V_{2})} w^{'} (kamu, v) = \sum_{(kamu, v) \in E (V_{1}, V_{2})} (\frac{w (kamu, v)}{HAI P T} + \frac{1}{k}) = 1 + \frac{| E (V_{1}, V_{2}) |}{k} \leq 2.

$\sum_{(u,v) \in E(V_1, V_2)} w'(u,v) = \sum_{(u,v) \in E(V_1, V_2)} \left(\frac{w(u,v)}{OPT} + \frac{1}{k}\right) = 1 + \frac{|E(V_1,V_2)|}{k} \leq 2.$

Algoritme kami menemukan potongan minimum - terarah dalam dengan bobot tepi . Biaya pemotongan ini paling banyak . Karenanya, potongan memotong paling banyak tepi . Biaya pemotongan paling banyak $s$ $t$ $(V_1', V_2')$ $G$ $w'$ $2$ $(V_1', V_2')$

E (V_{1}^{'}, V_{2}^{'}) = \sum_{(kamu, v) \in E (V_{1}^{'}, V_{2}^{'})} 1 \leq k \sum_{(kamu, v) \in E (V_{1}^{'}, V_{2}^{'})} w^{'} (kamu, v) \leq 2 k

$E(V_1', V_2') = \sum_{(u,v)\in E(V_1',V_2') } 1 \leq k \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2k$

\sum_{(kamu, v) \in E (V_{1}^{'}, V_{2}^{'})} w (kamu, v) \leq HAI P T \sum_{(kamu, v) \in E (V_{1}^{'}, V_{2}^{'})} w^{'} (kamu, v) \leq 2 HAI P T .

$\sum_{(u,v)\in E(V_1',V_2')} w(u,v) \leq OPT \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2OPT.$

Yury
sumber

Terima kasih banyak. Algoritma Anda sangat menarik dan berwawasan luas. Sayangnya tampaknya algoritma pendekatan bicriteria tidak cukup bagi kami, karena kami membutuhkan setiap solusi perkiraan agar layak dengan kendala kardinalitas. Apakah Anda tahu jika ada hasil yang diketahui dalam literatur? Terima kasih lagi!

Steven

Dengan menggunakan pendekatan ini, Anda bisa mendapatkan aproksimasi. Mungkin, Anda juga bisa mendapatkan pendekatan menggunakan LP. Tetapi mendapatkan sesuatu yang lebih baik dari itu tampaknya cukup sulit. Secara khusus, ada kesenjangan integral LP untuk relaksasi LP alami. Misalkan . Hubungkan ke dengan tepi berat 1 masing-masing, sambungkan ke dengan tepi berat 0. Solusi kombinatorial yang optimal memiliki biaya . Solusi LP optimal menetapkan untuk tepi dari ke , dan

k

$k$

(k + 1) / 2

$(k+1)/2$

V = s, t, x

$V={s,t,x}$

s

$s$

x

$x$

(k + 1) / 2

$(k+1)/2$

x

$x$

t

$t$

k + 1

$k+1$

(k + 1) / 2

$(k+1)/2$

x_{e} = 2 / (k + 1)

$x_e=2/(k+1)$

s

$s$

x

$x$

x_{e} = 1 - 2 / (k + 1)

$x_e=1-2/(k+1)$ ke tepi dari ke . Biayanya . Kesenjangannya adalah .

x

$x$

t

$t$

1

$1$

(k + 1) / 2

$(k+1)/2$

Yury

(k + 1) / 2

$(k+1)/2$

Algoritma pendekatan untuk Cut Minimum yang Diarahkan dengan Kendala Kardinalitas

Jawaban: