Új típusú min-max tételek a kombinatorikus optimalizálásban

Új típusú min-max tételek a kombinatorikus optimalizálásban Frank András (Egerváry Kutatócsoport, ELTE TTK)

Budapest 2016 október 19

Frank András (ELTE, EGRES)

Új típusú min-max tételek

Akadémiai székfoglaló

1 / 45

Kombinatorikus optimalizálás Fo˝ cél: ˝ olyan algoritmusok tervezése, melyek tengernyi lehetoség közül ˝ gyorsan választják ki a legkedvezobbet Példa: GPS: hogyan lehet leghamarabb eljutni A-ból B-be A GPS matematikai alapja: Dijkstra algoritmusa legolcsóbb út megkeresésére gráfban




2 / 45

Hatékony (jó, gyors) algoritmusok az algoritmus legyen véges, de . . . gyakorlati alkalmazásokban ez kevés polinomiális algoritmus: a lépés-szám az input-méret egy hatványával korlátozható például: Dijkstra algoritmusa n pontú gráfon ≤ n2 lépést igényel (holott az utak száma O(n!) is lehet!)

⇒ kevés problémára van polinomiális algoritmus és sokra nincs




3 / 45

Hatékony algoritmusok

Edmonds alapveto˝ felismerése (1965): I am claiming, as a mathematical result, the existence of "a good" algorithm for finding . . . "good" = polinomiális lépés-számú

fo˝ célunk: polinomiális algoritmusok tervezése és matematikai hátterük feltárása




4 / 45

Két nagy probléma-osztály (A) NPC: NP-teljes [sejtés: nincs polinomiális algoritmus] ˝ (B) P: Polinom idoben megoldható

(A1) leghosszabb st-út (B1) legrövidebb st-út (Dijkstra) ˝ ˝ részgráfja (A2) digráf legolcsóbb erosen összefüggo˝ (=eros) (B2) irányítatlan gráf legolcsóbb összefüggo˝ részgráfja (Kruskal) ˝ (A3) digráf erossé tevése min-költségu˝ új élek hozzáadásával ˝ (B3) digráf erossé tevése min-költségu˝ régi élek megfordításával (Fr.: How to make a digraph strongly connected, 1981)




5 / 45

˝ Erosen összefüggo˝ digráfok

˝ NEM erosen összefüggo˝

=====================================================

˝ erosen összefüggo˝




6 / 45

˝ Erosen összefüggo˝ digráfok Z

˝ NEM erosen összefüggo˝

Z-be nem lehet bejutni

=====================================================

˝ erosen összefüggo˝




6 / 45

I. RÉSZ "régi" típusú kombinatorikus min-max és megengedettségi tételek amikor a költséges/súlyozott változat is kezelheto˝




7 / 45

Korai min-max tételek

˝ Tétel (Konig, 1931) Páros gráfban (=bigráf) a diszjunkt élek max száma = az éleket lefogó pontok min száma. Tétel (Menger változat, 1927) Irányított gráfban (=digráf) az élidegen st-utak max száma = az st-utakat lefogó élek min száma.




8 / 45

Súlyozott min-max tételek

Tétel (Egerváry változat, 1931) Élsúlyozott bigráfban a párosítások max w-súlya = w-t lefogó nem-negatív pont-súlyozások min összértéke.

Tétel (Ford + Fulkerson, 1962) Digráfban k élidegen st-út min összköltsége = P max{k π(t) − uv ∈A [π(v ) − π(u) − c(uv )]+ : π : V → R, π(s) = 0}.




9 / 45

Min-max kontra megengedettség ˝ Konig másképp: páros gráfban nem létezik µ élu˝ párosítás ⇔ az éleket le lehet fogni µ-nél kevesebb ponttal

megengedettségi tétel (jó karakterizáció, szükséges és elegendo˝ feltétel) a min-max tétel ekvivalens átfogalmazása

mire jók a min-max vagy megengedettségi tételek ??? mi közük az algoritmusokhoz??? Frank András (ELTE, EGRES)



10 / 45

Algoritmushoz megállási szabály

(amikor mohó algoritmus vagy dinamikus programmozás nem segít)

˝ könnyen ellenorizhet o˝ igazolványt ad a végeredmény helyességére

˝ a megállási szabály ⇒ egy algoritmus konstruálását megelozi (=min-max vagy megengedettségi tétel) megtalálása




11 / 45

Háttér: hálózati folyamok

alapok: Ford és Fulkerson (1956) max-folyam min-vágás tétele ˝ Hoffman (1960) tétele megengedett áram létezésérol ˝ a költséges/súlyozott változatok is kezelhetok ˝ ⇒ bigráfok és digráfok fokszám-korlátos részgráfjai (pl. Konig tétele)




12 / 45

Háttér: lineáris programmozás + teljes unimodularitás (TU) a Q mátrix TU: ∀ aldetermináns (0, ±1)-értéku˝ Tétel (Lp dualitás TU mátrixokra) max{cx : Qx ≤ b, x ≥ 0} = min{by : yQ ≥ c, y ≥ 0} Ha Q TU és b, c egészértéku, ˝ akkor az optimumok egész vektoron is felvétetnek. ez a poliéderes kombinatorika kiinduló pontja

⇒ ∀ hálózati folyamos min-max tétel (pl. Egerváry tétele)




13 / 45

Amikor a hálózati folyamok nem segítenek irányítatlan gráfban: 1

∃ k élidegen feszíto˝ fa ⇐⇒ . . . [jó karakterizálás: Tutte, 1961]

2

˝ fokú ⇐⇒ ∃ feszíto˝ fa, mely egy stabil halmaz pontjaiban eloírt ... [jó karakterizálás: Lovász, 1970]

??? algoritmus ???

matroidok segítenek Frank András (ELTE, EGRES)



14 / 45

Súlyozatlan matroid optimalizálás alapok: Edmonds + Fulkerson (1965) min-max tétele k matroid esetén k független halmaz uniójának maximális elemszámáról Edmonds (1970) min-max tétele 2 matroid közös függetlenjeinek maximális elemszámáról mindkét bizonyítás polinomiális algoritmust ad . . . ˝ és ezek használhatók az elobbi (és egyéb) gráf problémákban ˝ a matroid r rangfüggvénye szubmoduláris fo˝ mozgató ero: r (X ) + r (Y ) ≥ r (X ∩ Y ) + r (X ∪ Y )




15 / 45

Súlyozott matroid optimalizálás 1 matroid bázisainak max ˆr (w) súlya keresheto˝ mohó algoritmussal 2 matroid max súlyú közös bázisa? Poliéderes kombinatorikai megközelítés: Qx ≤ b rendszer teljesen duálisan egészértéku˝ (TDI): ha a max {cx : Qx ≤ b} primál program duálisának ∀ egész c-re ∃ egész optimális megoldása. Tétel (Hoffman 1974, Edmonds + Giles 1976) TDI rendszer esetén a primál lineáris program optimuma is egész vektoron felvétetik.




16 / 45

Súlyozott matroid optimalizálás Tétel (Edmonds, 1979) Az {x ≥ 0, xe(Z ) ≤ min{r1 (Z ), r2 (Z ) : Z ⊆ S} lineáris rendszer TDI. Edmonds: min-max tétel + polinomiális algoritmus egyszerubb ˝ min-max tétel: Tétel Két matroid közös bázisainak max w-súlya = min{ˆr1 (w1 ) + ˆr2 (w2 ) : w1 + w2 = w}. egyszerubb ˝ algoritmust eredményez: (Fr.: A weighted matroid intersection algorithm, (1981)) Frank András (ELTE, EGRES)



17 / 45

Két aspektus szub- és szupermoduláris függvényekhez, matroidokhoz új tételek, algoritmusok létrehozása alkalmazásokhoz: matroidok + szubmoduláris függvények konstrukciója, felismerése például: digráfban keressünk legolcsóbb gyökeresen k -összefüggo˝ részgráfot (k = 1-re: Chu és Liu (1965), Fulkerson (1974)) Tétel (Fr. 2009) Egy digráf minimális gyökeresen k -összefüggo˝ részgráfjai két matroid közös bázisait alkotják. ⇒ alkalmazható a súlyozott matroid metszet algoritmus Frank András (ELTE, EGRES)



18 / 45

Amikor a matroidok sem segítenek

˝ digráfot ad D = (V , A) digráfban F ⊆ A kötés, ha megfordítása eros Tétel (Lucchesi + Younger, 1978) Kötés min elemszáma = élidegen egyirányú vágások max száma.

Tétel (Nash-Williams, 1960) ˝ G gráfnak ∃ k-élösszefüggo˝ irányítása ⇔ G 2k -élösszefüggo.




19 / 45

Szubmoduláris áramok: hálózat + matroid optimalizálás

D = (V , A): digráf, b: keresztezo˝ szubmoduláris x : A → R a szubmoduláris áram: %x (Z ) − δx (Z ) ≤ b(Z ) ∀ Z ⊆ V f ≤x ≤g Tétel [Edmonds + Giles, 1977)] Ez a rendszer TDI.




20 / 45

Szubmoduláris áramok Tétel (Edmonds + Giles, 1977) Az egészértéku˝ szubmoduláris áramok min c-költsége = a duális lineáris program maximuma. algoritmus: Cunningham + Fr. (1985) Tétel (Fr. 1982) ∃ egész szubmoduláris áram ⇔ e %f (Z ) − δg (Z ) ≤ b(F) minden Z ⊆ V -re és Z ∀ F fa-kompozíciójára. a bizonyítás algoritmikus az összes eddigi min-max és megengedettségi tétel következmény Frank András (ELTE, EGRES)



21 / 45

˝ A poliéderes kombinatorika elonye és hátránya ˝ a poliéderes kombinatorika elonye: ahol az elemszám optimalizálást tudja kezelni, ott a költséges optimalizálást is tudja a poliéderes kombinatorika hátránya: ahol az elemszám optimalizálást tudja kezelni, ott a költséges optimalizálást is tudja

??? van amikor az elemszám optimalizálásra van min-max tétel és algoritmus, míg a költséges változat NP-teljes Frank András (ELTE, EGRES)



22 / 45

II. RÉSZ új típusú kombinatorikus min-max és megengedettségi tételek amikor a költséges/súlyozott változat NP-teljes




23 / 45

Egyszeru˝ páros gráfok Tétel (Gale + Ryser, 1957) e S (S) = m e T (T ) = γ] ∃ egyszeru˝ bigráf ˝ (mS , mT ) fokszám eloíráshoz [m

e S (X ) + m e T (Z ) − |X ||Z | ≤ γ, ha X ⊆ S, Z ⊆ T . ⇐⇒ m folyamokból (is) következik (a fokszám-korlátos és a költséges alak is) ====================================================== Tétel (Ryser: max tag-rang (term-rank) tétel, 1958) ∃ (mS , mT ) fokszám-sorozatú egyszeru˝ bigráf µ élu˝ párosítással ⇐⇒ e S (X ) + m e T (Z ) − |X ||Z | + (µ − |X | − |Z |)+ ≤ γ, ha X ⊆ S, Z ⊆ T . m (eredetileg (0, 1)-mátrixokra fogalmazva) Frank András (ELTE, EGRES)



24 / 45

Ford + Fulkerson: Flows in Networks (1962), 89. oldal: "Neither term rank problem appears amenable to flow approach" magyarázat 50 év után: a max tag-rang probléma költséges változata NP-teljes (Dürr, Guinez, Matamala, 2012) így folyamokból NEM következhet

probléma: fokszám-korlátos max tag-rang ??




25 / 45

˝ ˝ növelés Erosen összefüggové

Tétel (Eswaran + Tarjan, 1976) ˝ ˝ növelheto˝ ⇔ D0 = (V , A0 ) digráf ≤ γ új éllel erosen összefüggové ˝ mind a forrás-, mind a nyelo-komponensek száma ≤ γ. A költséges változat NP-teljes, még üres A0 -ra is ˝ fokszám-eloírt ˝ digráffá ?? probléma: D0 növelése egyszeru, ˝ eros,




26 / 45

˝ növelés Irányítatlan k -él-összefüggové Tétel (Watanabe és Nakamura, 1987) ˝ növelheto˝ (k ≥ 2) ⇔ G0 gráf γ új éllel k-él-összefüggové q X

[k − d0 (Vi )] ≤ 2γ

i=1

a csúcsok minden {V1 , . . . , Vq } rész-partíciójára. a cikk 50 oldalas, a bizonyítás nem algoritmikus Fr.: Augmenting graphs to meet edge-connectivity requirements, 1992 szupermoduláris függvényeket használ: rövid, algoritmikus bizonyítás ˝ + általánosítás lokális él-összefüggoség növelésre + . . . Frank András (ELTE, EGRES)



27 / 45

˝ növelés Irányított k -él-összefüggové ˝ Eswaran + Tarjan általánosítása tetszoleges k ≥ 1-re: Tétel (Fr. 1992) ˝ növelheto˝ ⇔ D0 digráf γ új éllel k-él-összefüggové q X

[k − %0 (Vi )] ≤ γ és

i=1

q X

[k − δ0 (Vi )] ≤ γ

i=1

a csúcsok minden {V1 , . . . , Vq } rész-partíciójára. a valódi probléma a háttérben: szupermoduláris függvények fedése digráffal




28 / 45

Szupermoduláris függvény fedése digráffal a D digráf fedi a p halmazfüggvényt, ha %D (X ) ≥ p(X ) ∀ X ⊆ V -re

Tétel (Fr. 1994, szupermoduláris élfedés, gyenge alak) A p keresztezo˝ szupermoduláris függvény fedheto˝ γ irányított éllel ⇔ q X i=1

p(Vi ) ≤ γ és

q X

p(V − Vi ) ≤ γ

i=1

minden {V1 , . . . , Vq } részpartícióra. legelso˝ szupermoduláris függvényekre vonatkozó jó karakterizáció, amelynek költséges verziója NP-nehéz Frank András (ELTE, EGRES)



29 / 45

Szupermoduláris függvény fedése mire jó ez az absztrakt alak? ˝ fokszám-korlátos él-összefüggoség növelés ˝ él-összefüggoség növelés egy terminál halmazon belül fo˝ érdem: beindított egy teljesen új kutatási irányt ⇒ Fr. + Király, A survey on covering supermodular functions in: Research Trends in Combinatorial Optimization, (2009) Springer

pp. 87–126




30 / 45

Szupermoduláris függvény fedése irányítatlan gráffal és hipergráffal p: szimmetrikus keresztezo˝ szupermoduláris függvény Watanabe-Nakamura absztrakt alakja és kiterjesztései: Benczúr + Fr. (1999): p fedése min élszámú irányítatlan gráffal Fleiner + Jordán (1999): (0, 1)-értéku˝ p fedése min élszámú uniform hipergráffal Király T. (2004): p fedése min élszámú uniform hipergráffal Szigeti (1999): p fedése min össz-méretu˝ hiperéllel




31 / 45

˝ alakja A szupermoduláris élfedési tétel eros

p: ST -keresztezo˝ szupermoduláris halmaz-függvény ˝ alak) Tétel (Frank + Jordán, 1995, szupermoduláris él-fedés, eros A p-t fedo˝ ST -élek min száma = P max{ [p(Z ) : Z ∈ I] : I ST -él-független halmazrendszer}. ˝ motiváció: irányított pont-összefüggoség növelés kiderült: számos egyéb alkalmazás




32 / 45

˝ növelés Irányított k -pont-összefüggové Tétel (Fr. + Jordán, 1995) ˝ tevéséhez kello˝ új élek min száma = A D0 digráf k-összefüggové P max{ [p(X ) : X ∈ I] : I él-független pár-halmaz rendszer}.

pár-halmaz: X = (XK , XB ), XB ⊆ XK ⊂ V , "hiánya": ( k − (|XK | − |XB |) ha %0 (X ) = 0 p(X ) := 0 ha %0 (X ) > 0 algoritmus: Fr. és Végh (2008) eggyel növelés, Benczúr és Végh (2008) általános növelés Frank András (ELTE, EGRES)



33 / 45

Kombinatorikus geometriai következmények




34 / 45

Kombinatorikus geometriai következmények b

b b

b b b




34 / 45

Kombinatorikus geometriai következmények b

b b

b b b




34 / 45

Kombinatorikus geometriai következmények ⇒ ˝ 1984) Tétel (Gyori, ˝ Egy P függolegesen konvex síkbeli derékszögu˝ poligont fedo˝ téglalapok min száma = a P-beli független pontok max száma. általánosítás: P hengeren van (Fr. + Jordán ’95) algoritmus: Fr. ’99 ⇒ Soto és Telha (’14): min-max tétel diszjunkt téglalapok max számáról




35 / 45

Páros gráfok részgráfjai ⇒ Tétel (Hartvigsen + Király, 1999-2006) Bigráfban a négyszögmentes 2-párosítások max élszáma = min . . . Tétel (Fr. 2003) G = (S, T ; E)-ben a max Kt,t -mentes t-párosítás élszáma = min{[t|Z | + i((S ∪ T ) − Z ) − ct (Z ) : Z ⊆ S ∪ T }. i(X ): az X által feszített élek száma ct (Z ): a G − Z Kt,t -komponenseinek száma

algoritmus: Pap Gy. (2007)




36 / 45

Egyéb korábbi következmények

bigráf max "nagy" bi-klikk mentes részgráfja ˝ növelése T -n belül digráf k -összefüggové ˝ fokszám-korlátos összefüggoség növelés

˝ digráf létezése ⇒ k -összefüggo˝ fokszám-eloírt (lehet párhuzamos él!)




37 / 45

Friss következmények ˝ digráf? kérdés: mikor ∃ egyszeru˝ k -összefüggo˝ fokszám-eloírt

(irányítatlan gráfra: Wang + Kleitman, 1972) általánosabban: mi van, ha egyszeru˝ digráffal akarjuk p-t fedni? BAJ: p fedése NP-teljes problémákat tartalmaz ˝ JÓSZERENCSE: fontos speciális esetek kezelhetok




38 / 45

˝ egyszeru˝ digráfok Fokszám-eloírt

Hálózati folyamokból: Tétel (Gale + Ryser) ˝ Adott (mo , mi ) fokszám-eloíráshoz ∃ egyszeru˝ digráf ⇐⇒ e o (Z ) + m e i (X ) − |X ||Z | + |X ∩ Z | ≤ γ, ha X , Z ⊆ V . (∗) m




39 / 45

˝ egyszeru˝ k -összefüggo˝ digráfok Fokszám-eloírt k =1 Tétel (Hong, Liu, Lai, 2016) ˝ digráf az (mo , mi ) fokszám-eloíráshoz ˝ ∃ egyszeru˝ eros ⇐⇒ e o (Z ) + m e i (X ) − |X ||Z | + 1 ≤ γ, diszjunkt ∅ ⊂ X , Z ⊂ V -re. (∗) és m ˝ Tetszoleges k ≥ 1: Tétel (Bérczi + Fr. 2016) ˝ ∃ k -pont-összefüggo˝ egyszeru˝ digráf az (mo , mi ) fokszám-eloíráshoz ⇐⇒ e o (Z ) + m e i (X ) − |X ||Z | + k ≤ γ, különbözo˝ X , Z ⊂ V -re. (∗) és m




40 / 45

˝ élszámú fenyvesek pakolása Eloírt

Tétel (Edmonds, 1973) ˝ Gyökeresen k-él-összefüggo˝ digráfban ∃ k diszjunkt feszíto˝ fenyo. általánosítás: Tétel (Bérczi + Fr. 2016) D digráfban ∃ diszjunkt B1 , . . . , Bk fenyvesek, melyekre |Bj | = µj ⇐⇒ P P [%D (Vi ) : i = 1, . . . , q] ≥ [(q − (n − µj )+ : j = 1, . . . , k ] a csúcsok ∀ {V1 , . . . , Vq } rész-partíciójára




41 / 45

Ryser max tag-rang tételének általánosítása

Tétel (Bérczi + Fr. 2016) ∃ egyszeru˝ G = (S, T ; E) bigráf, melyre f ≤ dG ≤ g és G-ben van µ élu˝ párosítás ⇐⇒ eS (S − X ) − efT (Z ) + |X ||Z | + |X | + |Z | ≥ µ és g eT (T − Z ) − efS (Z ) + |X ||Z | + |X | + |Z | ≥ µ g minden X ⊆ S, Z ⊆ T -re

∃ algoritmikus bizonyítás is




42 / 45

Köszönetnyilvánítás ˝ lettek egykori szakdolgozók és doktoranduszok, akik társ-szerzoim Bárász Misi

Benczúr Andris

Becker Johanna

Bérczi Kristóf

˝ Dóri Erdos

Fleiner Tamás

Jordán Tibi

Király Csabi

Király Tamás

Kun Krisztián

Miklós Zoli

Pap Juli

Szabó Jácint

Szego˝ Laci

Szigeti Zoli

Tardos Éva

Végh Laci

Végh Zoli




43 / 45

Köszönetnyilvánítás ˝ további hazai társ-szerzok ˝ Péter Erdos

Gyárfás Andris

Sebo˝ Andris

Király Zoli

Székely Laci

akik a munkámat mindvégig figyelemmel kísérték Simonovits Miki és Sós Vera

˝ akik a körülményekhez alapvetoen járultak hozzá Recski Andris és Bernhard Korte




44 / 45

Köszönetnyilvánítás

akik az induláskor dönto˝ lökést adtak Rábai Imre és Pósa Lajos

˝ de legfoképp Lovász Laci




45 / 45

Új típusú min-max tételek a kombinatorikus optimalizálásban

Recommend Documents