Przybliżone twierdzenie o maksymalnym przepływie i minimalnym cięciu

Przybliżone twierdzenia o maksymalnym przepływie i minimalnym cięciu to twierdzenia matematyczne w teorii przepływu w sieci . Zajmują się zależnością między maksymalnym natężeniem przepływu („max-flow”) a minimalnym odcięciem („min-cut”) w problemie przepływu wielu towarów . Twierdzenia umożliwiły opracowanie algorytmów aproksymacyjnych do wykorzystania w dzieleniu grafów i powiązanych problemach.

Problem przepływu wielu towarów

„Towarem” w problemie przepływu sieci jest para węzłów źródłowych i ujścia . W problemie z przepływem wielu towarów istnieje k≥ 1 własne źródło ujście popyt . . Celem jest jednoczesne skierowanie jednostek towaru i z do t dla każdego ja , } taka, że ​​całkowita ilość wszystkich towarów przechodzących przez dowolną krawędź nie jest większa niż jej pojemność. (W przypadku krawędzi niekierowanych suma przepływów w obu kierunkach nie może przekroczyć przepustowości krawędzi). W szczególności problem przepływu 1 towaru (lub pojedynczego towaru) jest również znany jako problem maksymalnego przepływu . Zgodnie z algorytmem Forda-Fulkersona , przepływ maksymalny i minimalny są zawsze równe w problemie przepływu 1 towaru.

Maksymalny przepływ i minimalne cięcie

W problemie przepływu wielu towarów max-flow jest maksymalną wartością f , gdzie f jest wspólnym ułamkiem każdego kierowanego towaru, tak że jednostek towaru ja \ mogą być jednocześnie kierowane dla każdego i bez naruszania jakichkolwiek ograniczeń pojemności. min-cut minimum wszystkich cięć stosunku cięcia do zapotrzebowania cięcia. Maksymalny przepływ jest zawsze ograniczony górną granicą minimalnego odcięcia w przypadku problemu z przepływem wielu towarów.

Jednolity problem przepływu wielu towarów

W jednolitym problemie przepływu wielu towarów istnieje towar dla każdej pary węzłów, a popyt na każdy towar jest taki sam. (Bez utraty ogólności, popyt na każdy towar jest równy jeden.) Bazowa sieć i możliwości są dowolne.

Problem przepływu wielu towarów

mi ) . Popyt na towar między węzłami u i v jest iloczynem wag węzła u i węzła v . Problem jednolitego przepływu wielu towarów jest szczególnym przypadkiem problemu przepływu wielu towarów, dla którego waga jest ustawiona na 1 dla wszystkich węzłów. u ∈ .

Dualność programowania liniowego

Ogólnie rzecz biorąc, podwójny problem przepływu wielu towarów dla grafu G to problem przydzielenia ustalonej ilości ciężaru (gdzie ciężary można uznać za odległości) do krawędzi G, tak aby zmaksymalizować skumulowaną odległość między źródłem a ujściem pary.

Historia

Badania nad zależnością między przepływem maksymalnym a przepływem minimalnym w problemie przepływu wielu towarów cieszą się dużym zainteresowaniem od czasu uzyskania przez Forda i Fulkersona wyniku dla problemów przepływu 1-towarowego. Hu wykazał, że maksymalny przepływ i minimalny przepływ są zawsze równe dla dwóch towarów. Okamura i Seymour zilustrowali problem przepływu 4 towarów, przy czym maksymalny przepływ wynosi 3/4, a min-cut równy 1. Shahrokhi i Matula udowodnili również, że maksymalny przepływ i min-cut są równe, pod warunkiem, że podwójny problem przepływu spełnia określony warunek cięcia w jednolitym problemie przepływu wielu towarów. Również wielu innych badaczy przedstawiło konkretne wyniki badań w podobnych problemach

sieci maksymalny przepływ mieści się w zakresie współczynnika cięcia , ponieważ każdy towar można zoptymalizować osobno, wykorzystując każdej krawędzi. Nie jest to dobry wynik zwłaszcza w przypadku dużej ilości towarów.

Przybliżone twierdzenia o maksymalnym przepływie i minimalnym cięciu

Twierdzenia o problemach jednolitego przepływu wielu towarów

Istnieją dwa twierdzenia po raz pierwszy wprowadzone przez Toma Leightona i Satisha Rao w 1988 r., a następnie rozszerzone w 1999 r. Twierdzenie 2 daje ściślejsze ograniczenie w porównaniu z twierdzeniem 1.

Twierdzenie 1. Dla dowolnego n istnieje n -węzłowy problem jednolitego przepływu wielu towarów z maksymalnym przepływem f i minimalnym cięciem dla których .

Twierdzenie dowolnego gdzie f jest maksymalnym przepływem, a minimalnym cięciem problemu jednolitego przepływu wielu towarów

Aby udowodnić Twierdzenie 2, należy omówić zarówno przepływ maksymalny, jak i minimalny. W przypadku maksymalnego przepływu należy zastosować techniki z teorii dualności programowania liniowego. Zgodnie z teorią dualizmu programowania liniowego, optymalna funkcja odległości daje całkowitą wagę równą maksymalnemu przepływowi problemu jednorodnego przepływu wielu towarów. W przypadku cięcia min należy postępować zgodnie z 3-etapowym procesem:

Etap 1: Rozważ podwójny problem jednorodnego przepływu towarów i użyj optymalnego rozwiązania do zdefiniowania wykresu z etykietami odległości na krawędziach.

Etap 2: Rozpoczynając od źródła lub ujścia, powiększaj region na wykresie, aż znajdziesz cięcie o wystarczająco małej pojemności, oddzielające pierwiastek od jego partnera.

Etap 3: Usuń region i powtórz proces etapu 2, aż wszystkie węzły zostaną przetworzone.

Uogólniony na problem przepływu wielu towarów

Twierdzenie 3. Dla dowolnego problemu przepływu wielu towarów z k towarami gdzie f jest maksymalnym przepływem, a cięciem problemu przepływu wielu towarów produktu.

Metodologia dowodu jest podobna jak w przypadku Twierdzenia 2; główna różnica polega na uwzględnieniu wagi węzłów.

Rozszerzony na ukierunkowany problem przepływu wielu towarów

W problemie ukierunkowanego przepływu wielu towarów każda krawędź ma kierunek, a przepływ jest ograniczony do ruchu w określonym kierunku. W zadaniu ukierunkowanego jednorodnego przepływu wielu towarów popyt jest ustawiony na 1 dla każdej skierowanej krawędzi.

Twierdzenie 4. Dla dowolnego skierowanego problemu jednolitego przepływu wielu towarów z n węzłami , gdzie f jest przepływem maksymalnym, a minimalnym cięciem problemu jednolitego przepływu wielu towarów

Główna różnica w metodologii dowodu w porównaniu z Twierdzeniem 2 polega na tym, że teraz należy wziąć pod uwagę kierunki krawędzi podczas definiowania etykiet odległości na etapie 1, a przy powiększaniu regionów na etapie 2 więcej szczegółów można znaleźć w.

Podobnie w przypadku problemu przepływu wielu towarów mamy następujące rozszerzone twierdzenie:

Twierdzenie 5. Dla dowolnego problemu przepływu wielu towarów skierowanych z k towarami , gdzie f jest przepływem maksymalnym, a jest ukierunkowanym minimalnym cięciem problemu przepływu wielu

Zastosowania algorytmów aproksymacyjnych

Powyższe twierdzenia są bardzo przydatne do projektowania algorytmów aproksymacyjnych dla problemów NP-trudnych , takich jak problem podziału grafu i jego odmiany. Poniżej przedstawiamy pokrótce kilka przykładów, a szczegółowe rozwinięcia można znaleźć w Leighton i Rao (1999).

Najrzadsze cięcia

Najrzadszy przekrój wykresu do iloczynu liczby węzłów oba składniki są zminimalizowane. -trudny i można go przybliżyć do najrzadszy problem cięcia z ważonymi krawędziami, ważonymi węzłami lub krawędzie można przybliżyć w ramach gdzie p wadze zgodnie z twierdzeniem 3, 4 i 5.

Zrównoważone cięcia i separatory

małe cięcie na wykresie, części o prawie równej wielkości Zwykle nazywamy cięcie b-zrównoważonym lub a ( b ,1 − b ) - separatorem (dla b ≤ 1/2 ) jeśli gdzie jest sumą wag węzłów w U . Jest to również NP-trudny . Algorytm aproksymacji został zaprojektowany dla tego problemu, a podstawową ideą jest to, że G ma b -zrównoważony krój rozmiaru S , a następnie znajdujemy b -zrównoważony krój rozmiaru dla dowolnego b' gdzie b ′ < b i b ′ ≤ 1/3 . Następnie powtarzamy proces, aby ostatecznie uzyskać wynik, że całkowita waga krawędzi w cięciu wynosi co najwyżej .

Problemy z układem VLSI

Podczas projektowania obwodu VLSI pomocne jest znalezienie układu o minimalnym rozmiarze. Taki problem często można modelować jako problem osadzania grafu. Celem jest znalezienie osadzania, dla którego obszar układu jest zminimalizowany. Znalezienie minimalnego obszaru układu jest również NP-trudne. Wprowadzono algorytm aproksymacji, a wynik jest optymalny razy

Problem z indeksem przekierowania

Biorąc pod uwagę -węzłowy wykres G i osadzenie w G , i in zdefiniował indeks przekazywania osadzania jako maksymalną liczbę ścieżek (każda odpowiadająca krawędzi przechodzą przez dowolny węzeł G . Celem jest znalezienie osadzania, które minimalizuje indeks przekazywania. możliwe jest powiązanie indeksów węzłów i przesunięcia krawędzi do dla każdego wykresu

Usuwanie krawędzi płaskich

Tragoudas używa algorytmu aproksymacji dla zrównoważonych separatorów, aby znaleźć zbiór G o ograniczonych stopniach daje w wyniku graf planarny, gdzie R jest minimalną liczbą krawędzi, które należy usunąć z G , zanim stanie się planarny . Pozostaje otwartym pytaniem, czy istnieje wielolog n razy optymalny algorytm aproksymacji dla R .