Přibližná věta o maximálním průtoku min - Approximate max-flow min-cut theorem

tento článek může být pro většinu čtenářů příliš technická na to, aby tomu rozuměli. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Leden 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Přibližný věty o maximálním průtoku a minimálním řezu jsou matematické návrhy v tok sítě teorie. Zabývají se vztahem mezi maximálním průtokem („max-flow“) a minimální řez ("min. řez") v a problém multikomoditního toku. Věty umožnily vývoj aproximační algoritmy pro použití v grafický oddíl a související problémy.

Problém toku více akomodit

„Komoditou“ v problému toku sítě je dvojice zdrojů a jímek uzly. V problému s multikomoditním tokem existují k≥1 komodity, každá s vlastním zdrojem ${ displaystyle s_ {i}}$, dřez ${ displaystyle t_ {i}}$a poptávka ${ displaystyle D_ {i}}$. Cílem je současně směrovat ${ displaystyle D _ { text {i}}}$ komoditní jednotky i z ${ displaystyle s_ {i}}$ na ${ displaystyle t_ {i}}$ pro každého i, takže celkové množství všech komodit procházejících jakoukoli hranou není větší než jejich kapacita. (V případě neorientovaných hran nemůže součet průtoků v obou směrech překročit kapacitu hrany).^[1]Speciálně problém s tokem 1 komodity (nebo jedné komodity) je také známý jako problém s maximálním průtokem. Podle Algoritmus Ford-Fulkerson, maximální průtok a minimální řez jsou vždy stejné u problému s tokem 1 komodity.

Maximální průtok a minimální řez

U problému toku více akomodací maximální průtok je maximální hodnota F, kde F je společný zlomek každé komodity, která je směrována, taková ${ displaystyle fD _ { text {i}}}$ komoditní jednotky i lze směrovat současně pro každého i aniž by došlo k porušení jakýchkoli kapacitních omezení.min. řez je minimum všech řezů poměru ${ displaystyle varphi}$ kapacity řezu podle potřeby řezu. Max. průtok je vždy horně omezen min. řezem pro problém s více akomodací.

Jednotný problém toku více akomodací

V problému s jednotným tokem více akomodit existuje komodita pro každý pár uzlů a poptávka po každé komoditě je stejná. (Bez ztráty obecnosti je poptávka po každé komoditě nastavena na jednu.) Základní síť a kapacity jsou libovolné.^[1]

Problém toku produktu s více ubytováními

V problému toku produktu s více akomodacemi je pro každý uzel nezáporná váha ${ displaystyle v ve V}$ v grafu ${ displaystyle G = (V, E)}$. Poptávka po komoditě mezi uzly u a proti je součinem váhy uzlu u a uzel proti. Problém s jednotným tokem více akomodací je speciální případ problému s vícekanálovým tokem produktu, pro který je váha nastavena na 1 pro všechny uzly ${ displaystyle u ve V}$.^[1]

Dualita lineárního programování

Obecně platí, že dvojí problém toku více akomodit pro graf G je problém rozdělení pevného množství váhy (kde váhy lze považovat za vzdálenosti) k okrajům G takové, aby se maximalizovala kumulativní vzdálenost mezi páry zdroje a dřezu.^[1]

Dějiny

Výzkum vztahu mezi maximálním tokem a minimálním řezem problému toku více akomodit získal velký zájem od výsledku Forda a Fulkersona pro problémy s tokem 1 komodity. Hu^[2]ukázal, že maximální tok a minimální řez jsou vždy stejné pro dvě komodity. Okamura a Seymour^[3] ilustroval problém 4komoditního toku s maximálním tokem rovným 3/4 a minimálním řezem rovným 1. Shahrokhi a Matula^[4] také prokázal, že maximální průtok a minimální řez jsou stejné za předpokladu, že duální problém průtoku splňuje určitou podmínku řezu v jednotném problému průtoku více akomodací. Mnoho dalších vědců také ukázalo konkrétní výsledky výzkumu podobných problémů^[5][6][7]

U obecného problému s tokem v síti je maximální tok v rámci faktoru k min-cutu, protože každou komoditu lze optimalizovat samostatně pomocí ${ displaystyle 1 / k}$ kapacity každé hrany. To není dobrý výsledek, zejména v případě velkého počtu komodit.^[1]

Přibližné věty o maximálním průtoku min

Věty o problémech proudění jednotné více akomodace

Existují dvě věty, které poprvé představili Tom Leighton a Satish Rao v roce 1988^[8]a poté prodloužena v roce 1999.^[1] Věta 2 dává pevnější vazbu ve srovnání s větou 1.

Věta 1. Pro všechny n, tady je n-uzel problém rovnoměrného více akomoditního toku s maximálním průtokem F a min ${ displaystyle varphi}$ pro který ${ displaystyle f leq O left ({ frac { varphi} { log n}} right)}$.^[1]

Věta 2. U jakéhokoli problému s jednotným tokem více akomodací ${ displaystyle Omega left ({ frac { varphi} { log n}} right) leq f leq varphi}$, kde F je maximální průtok a ${ displaystyle varphi}$ je minimální řez problému rovnoměrného vícemístného toku.^[1]

K prokázání věty 2 je třeba diskutovat o maximálním i minimálním průtoku. Pro maximální tok je třeba použít techniky z teorie duality lineárního programování. Podle teorie duality lineárního programování má funkce optimální vzdálenosti za následek celkovou hmotnost, která se rovná maximálnímu toku problému rovnoměrného vícemístného toku. U minorezu je třeba dodržovat 3stupňový proces:^[1][6]

Fáze 1: Zvažte dvojí problém jednotného toku komodit a pomocí optimálního řešení definujte graf se značkami vzdálenosti na okrajích.

Fáze 2: Počínaje od zdroje nebo jímky, zvětšete oblast v grafu, dokud nenajdete řez dostatečně malé kapacity oddělující kořen od jeho partnera.

Fáze 3: Odeberte oblast a opakujte proces ve fázi 2, dokud nebudou zpracovány všechny uzly.

Zobecněno na problém toku produktu s více akomodacemi

Věta 3. Pro jakýkoli problém s multikomunitním tokem produktu s k komodity, ${ displaystyle Omega left ({ frac { varphi} { log k}} right) leq f leq varphi}$, kde F je maximální průtok a ${ displaystyle varphi}$ je minimální řez problému toku více akomodit produktu.^[1]

Metodika důkazu je podobná metodě pro Theorem 2; hlavním rozdílem je vzít v úvahu hmotnosti uzlů.

Rozšířeno na směrovaný problém toku více akomodací

V případě problému s směrovaným tokem více akomodací má každá hrana směr a tok je omezen na pohyb v určeném směru. V případě problému směrovaného rovnoměrného vícerodičového toku je požadavek nastaven na 1 pro každou směrovanou hranu.

Věta 4. Pro jakýkoli směrovaný jednotný problém toku více akomodací s n uzly, ${ displaystyle Omega left ({ frac { varphi} { log n}} right) leq f leq varphi}$, kde F je maximální průtok a ${ displaystyle varphi}$ je minimální řez problému rovnoměrného vícemístného toku.^[1]

Hlavní rozdíl v metodice důkazu ve srovnání s teorémem 2 spočívá v tom, že nyní je třeba při definování značek vzdáleností ve fázi 1 brát v úvahu směry okrajů a pro růst regionů ve fázi 2 lze nalézt další podrobnosti v.^[1]

Podobně pro problém toku produktů s více akomodacemi máme následující rozšířenou větu:

Věta 5. Pro jakýkoli směrovaný problém s vícenásobným tokem produktu s k komodity, ${ displaystyle Omega left ({ frac { varphi} { log k}} right) leq f leq varphi}$, kde F je maximální průtok a ${ displaystyle varphi}$ je směrovaný minimální řez problému toku více akomodit produktu.^[1]

Aplikace na aproximační algoritmy

Výše uvedené věty jsou velmi užitečné pro návrh aproximační algoritmy pro NP-tvrdé problémy, jako je grafický oddíl problém a jeho variace. Zde níže stručně představíme několik příkladů a podrobná rozpracování lze nalézt v Leighton a Rao (1999).^[1]

Nejmenší řezy

Nejmenší výřez grafu ${ displaystyle G = (V, E)}$ je oddíl, u kterého je minimalizován poměr počtu hran spojujících dvě rozdělené komponenty k součinu počtu uzlů obou komponent. Jedná se o NP-těžký problém a lze jej přiblížit uvnitř ${ displaystyle O ( log n)}$ faktor využívající větu 2. Rovněž problém nejspodnějšího řezu s váženými hranami, váženými uzly nebo směrovanými hranami lze aproximovat v rámci ${ displaystyle O ( log p)}$ faktor kde p je počet uzlů s nenulovou váhou podle vět 3, 4 a 5.

Vyvážené řezy a oddělovače

V některých aplikacích chceme najít malý výřez v grafu ${ displaystyle G = (V, E)}$ že rozděluje graf na kousky téměř stejné velikosti. Obvykle říkáme řez b-vyvážený nebo a (b,1 − b)-oddělovač (pro b ≤ 1/2) pokud ${ Displaystyle b pi (V) leq pi (U) leq (1-b) pi (V)}$ kde ${ displaystyle pi (U)}$ je součet hmotností uzlu v U. To je také NP-tvrdé problém. Pro tento problém byl navržen aproximační algoritmus,^[1] a hlavní myšlenkou je to G má b- vyvážený střih velikosti S, pak najdeme a b′- vyvážený střih velikosti ${ displaystyle O left (S log { frac {n} {b}} - b ' right)}$ pro všechny b ' kde b′ < b a b′ ≤ 1/3. Poté postup opakujeme a nakonec získáme výsledek, že celková hmotnost hran v řezu je maximálně ${ displaystyle O left ({ frac {S log n} {b-b '}} right)}$.

Problémy s rozložením VLSI

Při navrhování obvodu VLSI je užitečné najít rozložení minimální velikosti. Takový problém lze často modelovat jako problém s vložením grafu. Cílem je najít vložení, u kterého je minimalizována oblast rozvržení. Nalezení minimální oblasti rozložení je také NP-těžké. Byl zaveden aproximační algoritmus^[1] a výsledek je ${ displaystyle O ( log ^ {6} n)}$ krát optimální.

Problém s předáním indexu

Vzhledem k n-uzlový graf G a vložení ${ displaystyle K_ {n}}$ v G, Chung a kol.^[9]definoval index předávání z vložení je maximální počet cest (každá odpovídá okraji ${ displaystyle K_ {n}}$), které procházejí jakýmkoli uzlem G. Cílem je najít vložení, které minimalizuje index předávání. Použití přístupů pro vkládání^[1] je možné svázat uzel a indexy pro předávání hran s uvnitř ${ displaystyle O ( log n)}$-faktor pro každý graf G.

Rovinné mazání hran

Tragoudas^[10]používá aproximační algoritmus pro vyvážené oddělovače k ​​nalezení množiny ${ displaystyle O left ((R log n + { sqrt {nR}}) log { frac {n} {R}} right)}$hrany, jejichž odstranění z grafu omezeného stupně G má za následek rovinný graf, kde R je minimální počet hran, ze kterých je třeba odstranit G než se stane rovinným. Zůstává otevřenou otázkou, pokud existuje polylog n krát optimální aproximační algoritmus pro R.^[1]

Reference