Drugi najmniejszy

Czy coś wiadomo o drugim najmniejszym - -cut w sieci przepływowej? Lub, bardziej ogólnie, na temat tego problemu: $s$ $t$

Dane wejściowe: sieć i liczba , wszystkie w postaci binarnej. Wyjście: najmniejszy odcinek - . $N$ $k$
$k$ $s$ $t$

-tej najmniejszej - cięcia to jakiekolwiek - cięcia tak, że nie są dokładnie - kawałki, których moce $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ $t$

są parami różne i
naprawdę mniejszy niż pojemność . $(S,T)$

Chciałbym wiedzieć, jak można to obliczyć i czy można to zrobić skutecznie, jak w przypadku . $k=1$

cc.complexity-theory optimization max-flow-min-cut flow-problems Oliver Witt
źródło

Drugie najmniejsze cięcie można znaleźć, dodając

masy do wszystkich krawędzi w najmniejszym cięciu, a następnie obliczając nowy najmniejszy cięcie. Prawdopodobnie działa to tak długo, jak długo

jest zakodowane w jednostkowej (a na pewno dla stałej stałej

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

Nie rozumiem, jak to pomaga. Wyobraź sobie sieć ścieżek składającą się z trzech węzłów

tylko z dwoma krawędziami

. Ponadto, niech pojemności będą

. Oczywiste jest, że cięcia minimalne

i drugie najmniejsze cięcia

s

$s$

v

$v$

t

$t$

(s, v)

$(s,v)$

(v, t)

$(v,t)$

c (s, v) = 1

$c(s,v)=1$

c (v, t) = 2

$c(v,t)=2$

(s, v)

$(s,v)$

. Zwiększenie wydajności, jak opisano, ponownie dałoby

jako cięcie minimalne o wydajności

. Jak mam wywnioskować z tego drugie najmniejsze cięcie?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

Oliver Witt

Dodanie dolnej granicy na końcu cięcia jest nierównością liniową, wystarczy dodać jeden epsilon większy niż ograniczenie min i uruchomić LP. Możesz powtórzyć to k razy, aby uzyskać to, czego chcesz. Prawdopodobnie można to przekształcić jako modyfikację w sieci, ale jeszcze tego nie wypracowałem.

Kaveh

Widzę, jak to działa, jeśli

jest w kodowaniu jednoargumentowym. Co jeśli jest binarny? W tym przypadku modyfikacja sieci nie można zrobić w

iteracji.

k

$k$

k

$k$

Oliver Witt,

Wątpię, czy istnieje proste rozwiązanie, jeśli k jest binarne. Możemy sprawdzić, czy istnieje odcięcie czapki c, jak opisałem. Wydaje mi się, że w zasadzie liczy liczbę możliwych c, można podać, aby odnosić się do zliczania liczby dopasowań i prawdopodobnie # P-complete. (To tylko moja intuicja, a nie kłótnia.)

Kaveh

Drugi najmniejszy cięte, a ogólniej najmniejsze kawałki, można znaleźć w czasie wielomianowym w i wielkości sieci. Widzieć: $k$ $k$

HW Hamacher. Algorytm znalezienia najlepsze cięcie w sieci. Oper. Res. Łotysz. 1 (5): 186–189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 . $(K\cdot n^4)$ $k$

HW Hamacher, J.-C. Picard i M. Queyranne. Po znalezieniu najlepszych cięć w sieci. Oper. Res. Łotysz. 2 (6): 303–305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X . $K$

$K$

David Eppstein
źródło

k

$k$

k

$k$

Ja też to rozumiem: dozwolone są równe ciężary. To wydaje się nie odpowiadać na pytanie. Niemniej jednak nie byłem świadomy tych dokumentów, dzięki za to.

Oliver Witt

k

$k$

k

$k$

Drugi najmniejszy

Odpowiedzi: