Vektorösszegzési tételek és diszkrepanciák egy távközlési alkalmazással

Diplomamunka

Makai Márton alkalmazott matematikus hallgató

Témavezetők: Frank András egyetemi tanár, Király Zoltán egyetemi docens

Eötvös Loránd Tudományegyetem Természettudományi Kar Operációkutatási Tanszék

Budapest, 2001.

Tartalom

1 Bevezetés 2

2 Néhány alapvető jelölés 3

3 Az útátpakolási feladat 4

4 Korlátos vektorösszegzés és diszkrepanciák 7 4.1 A Steinitz-függvény végessége . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Diszkrepanciák és kerekítések 16

6 Diszkrepanciák néhány speciális ℓ_{p} normában 19 6.1 Általános becslések, és az ℓ_{1} norma speciális esete . . . . . . . . . . . . . 19 6.2 Az ℓ_{2} norma szépen viselkedik . . . . . . . . . . . . . . . . . . . . . . . . 20 6.3 ℓ_{∞} norma: a kellemetlen eset . . . . . . . . . . . . . . . . . . . . . . . . 22

7 Különböző normák 27

8 A Dvoretzky-függvény illetve a diszkrepancia egy általánosítása 30 8.1 Általános becslések és az ℓ_{1} eset . . . . . . . . . . . . . . . . . . . . . . . 30 8.2 Az ℓ_{2} norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 8.3 Az ℓ_{∞} eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8.4 Egy alkalmazás: MIP és torlódásminimalizálás osztatlan folyamban … 33

9 Dinamikus diszkrepanciák 37 9.1 Általános becslések, és ℓ_{1} norma . . . . . . . . . . . . . . . . . . . . . . 37

10 Kiegyensúlyozó játékok 39 10.1 A kiegyensúlyozó játék ℓ_{2} normában . . . . . . . . . . . . . . . . . . . . 40 10.2 ℓ_{∞} norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

11 Útátpakolás újra 44 11.1 Martingálok alkalmazása . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 11.2 A dinamikus eset derandomizációja és martingálok . . . . . . . . . . . . 46 11.3 Következmények az útátpakoláshoz szükséges kapacitásra . . . . . . . . 49

12 Mohó heurisztikák és a véletlen sorrend 52

13 Multi-color diszkrepanciák 54

14 Ütemezéselméleti alkalmazás:

korlátos vektorösszegzés a shop-ütemezésben 55

15 Függelék: néhány fontos egyenlőtlenség valószínűségszámításból 60

1 Bevezetés

Dolgozatunk kiindulópontja egy távközlési hálózatokban felmerülő átkonfigurálási probléma, az útátpakolási probléma, melyben az igényeket kielégítő útrendszer útjait kell valamilyen sorrendben egyenként kicserélni egy másik útrendszer útjaira, a kapacitásfeltétel megsértése nélkül. Amennyiben a rendelkezésre álló szabad kapacitás a hálózatban elegendően nagy, ilyen sorrendezést lehet találni. Dolgozatunk egyik célja, hogy minél kisebb korlátot szabjon a szükséges szabad kapacitás mennyiségére, s hogy ezen korláthoz algoritmust találjon megfelelő sorrend előállításához.

Ez a sorrendezési kérdés elvezet egy olyan korlátos vektorösszegzési feladathoz, melyben nulla összegű legfeljebb egy normájú vektorok egy olyan sorrendjét keressük, hogy az ilyen sorrendben vett összegzéskor minden részletösszeg normája kicsi legyen. A kérdés már korábban felmerült a funkcionálanalízisben amiben nagy szerepe volt Steinitz 1913ban megjelent cikkének. A dolgozatban megmutatjuk, hogy adható csak a normától és a dimenziótól függő korlát illetve megvizsgáljuk, hogy milyen jobb becslés adható, ha ismerjük a vektorok számát is. Az eredményeket átfogalmazzuk az eredeti útátpakolási problémára nyelvére is.

Rávilágítunk továbbá , hogy ez a vektorösszegzési feladat miként áll kapcsolatban a diszkrepanciaelméletben felmerülő diszkrét diszkrepancia feladatokkal, illetve dinamikus diszkrepancia feladatokkal. Az útátpakolásra kapott eredményekre erős hatással lesznek ezen vizsgálatok is. A dinamikus diszkrepanciafeladatoknál különbséget teszünk az offline és on-line változat között, ez utóbbi a kiegyensúlyozó játékokhoz (balancing game) áll közel, így ezekre is elvégzünk néhány egyszerűbb vizsgálatot.

Végül az alkalmazások között az eredeti útátpakolási probléma mellett megvizsgáljuk, hogy a korlátos vektorösszegzési feladat közelítő megoldására kapott garanciák hogyan alkalmazhatók az többgépes ütemezéselmélet nagy területét felölelő shop feladatok közelítő megoldására, így az open shop és flow shop feladatokra vonatkozó approximációs eredményekről írunk.

A diszkrepanciák vizsgálatánál közel kerülünk egy további alkalmazáshoz, az osztatlan folyam problémánál felmerülő torlódásminimalizálási feladathoz, s megnézzük, hogy korábbi vizsgálataink milyen eredményeket adnak erre a feladatra.

A dolgozat eszköztárában azonos szerepet kapnak lineáris algebrai meggondolások, s a diszkrepanciakérdések vizsgálatánal gyakran felbukkanó valószínűségi módszer. Az algoritmikus kérdések előtérbe kerülésével példákat mutatunk a valószínűségi módszer által garantált megoldások algoritmikus megkeresésére, derandomizációkra, ezzel a módszerrel sikerül előállítani az útátpakolási feladatra ismert legjobb megoldásunkat is.

Köszönöm témavezetőimnek, Frank Andrásnak és Király Zoltánnak, hogy egy gyakorlatban felmerülő kérdésen keresztül elvezettek egy ilyen érdekes területre. Szeretném megköszönni Bárány Imrének és T. Sós Verának, hogy segítettek elindulni a diszkrepanciák irodalmában és T. Sós Verának külön a véletlen struktúrák világában nyújtott segítséget. Köszönöm továbbá Fige Péternek az NP-teljességi bizonyításokban nyújtott segítségét. A dolgozat létrejöttét támogatta az ETIK (Egyetemközi Távközlési és Informatikai Központ).

2 Néhány alapvető jelölés

Elöljáróban álljon itt néhány jelölés illetve definíció. Definíció 2.1. Nemszimmetrikus félnormának hívunk egy t : ℝ^{m} → ℝ, t ≥ 0 függvényt, amire

1. t(x + y) ≤ t(x) + t(y), minden x, y ∈ ℝ^{m},

2. t(αx) = αt(x), minden x ∈ ℝ^{m}, α ≥ 0, szimmetrikus félnormának hívunk egy t : ℝ^{m} → ℝ, t ≥ 0 függvényt, amire

1. t(x + y) ≤ t(x) + t(y), minden x, y ∈ ℝ^{m}

2. t(αx) = |α|t(x), minden x ∈ ℝ^{m}, α ∈ ℝ, végül normának egy s : ℝ^{m} → ℝ, s ≥ 0 függvényt, amire

1. s(x) = 0 ⇔ x = 0,

2. s(x + y) ≤ s(x) + s(y), minden x, y ∈ ℝ^{m}

3. s(αx) = |α|s(x), minden x ∈ ℝ^{m}, α ∈ ℝ. A félnormákra illetve normákra a szokásnak megfelelően az ∥x∥_{s} = s(x), x ∈ ℝ^{m} jelölést használjuk.

A s egységgömmbjén a B_{s,m} = {z ∈ ℝ^{m} : ∥z∥_{s} ≤ 1} a halmazt értjük. Legyen továbbá B_{n,s,m} = B_{s,m}^{n} az egységgömbből vett n-elemű sorozatok halmaza. A B_{n,s,m} halmazra úgy is fogunk gondolni, mint az olyan m × n-es mátrixok halmazára, melyek minden oszlopa B_{s,m}-ből van. A természetes megfeleltetés miatt ez a kis pontatlanság megengedhető. Hasonlóan

B_{n,s,m}^{0} = {B ∈ B_{n,s,m} : ∑_{z∈B} z = 0} az ugyanilyen nullaösszegű sorozatok halmaza, illetve a megfelelő mátrixoké.

A dolgozatban gyakran használt normák. Az x = (x_{1}, x_{2}, …, x_{m})^{T} ∈ ℝ^{m} vektorra legyen 1 ≤ p < ∞ esetén

∥x∥_{ℓ_{p}} = (∑_{i=1}^{m} |x_{i}|^{p})^{1 ; p} ,

illetve

∥x∥_{ℓ_{∞}} = max_{1≤i≤m} |x_{i}|.

A természetes számok {1, 2, …, n} részhalmazát [n]-nel jelöljük. Az [n] alaphalmazon vett m-elemű halmazrendszerek halmazát jelölje F_{n,m}. Egy F ∈ F_{n,m} halmazrendszer incidenciamátrixán azt az m × n-es mátrixot értjük, melynek sorai az F halmazrendszer halmazainak karakterisztikus vektorai.

3 Az útátpakolási feladat

A dolgozat témájának körbejárásához a következő távközlési hálózatokban felmerülő újrakonfigurálási probléma adta az ötletet. Ez nagyon izgalmas és fontos feladat, hisz ha a teoretikus eredményeket nem is tudjuk maximálisan igába fogni, legalább tudni fogjuk, hogy milyen megoldások létezését és hatékony kiszámolhatóságát várhatjuk el a gyakorlatban.

Útátpakolási feladat. Az angol névnek (reroute sequence planning) megfelelően gyakran az RSP rövidítéssel fogunk élni, bár egy új feladatról lévén szó, valószínűtlen, hogy a szakirodalomban ez sok helyen szerepelne. Vegyünk egy távközlési hálózatot, ami legyen most egy irányítatlan gráf G = (V, E), az élhalmazon egy c : E → ℝ_{+} nemnegatív kapacitásfüggvénnyel. Az s_{i} és t_{i} pontok között felmerül rendre egy d_{i} nagyságú igény minden i-re, ahol 1 ≤ i ≤ n. Adott továbbá két útrendszer, P = (P_{1}, P_{2}, …, P_{n}) és Q = (Q_{1}, Q_{2}, …, Q_{n}), ahol P_{i} és Q_{i} mindkettő az s_{i} és t_{i} pontok között halad. Az igények együtt mind P-n, mind Q-n kielégíthetőek a kapacitásfeltétel megsértése nélkül (úgy, hogy az i. igényt az adott útrendszer i. útján vezetjük el). Magyarul, ha a P_{i}, Q_{i} utak incidenciavektorai rendre p_{i}, q_{i} akkor

∑_{i=1}^{n} d_{i}p_{i} ≤ c,

illetve

∑_{i=1}^{n} d_{i}q_{i} ≤ c.

(Itt úgy tekintünk c-re, mint egy |E|-dimenziós vektorra, melyben az e él által indexelt helyen c(e) áll.) Ebből úgy kapunk egy hálózatújrakonfigurálási problémát, hogy feltesszük, hogy kezdetben a P útrendszer útjain vannak elvezetve az igények, s valamilyen oknál fogva az utakat ki kell cserélni a Q rendszer útjaira, egyenként, úgy, hogy a köztes útrendszerek egyike se sértse meg a kapacitásfeltételt. A cél tehát az (1, 2, …, n) sorozat egy olyan π = (π_{1}, π_{2}, …, π_{n}) permutációját megkeresni, hogy a (Q_{π_{k}}(k ≤ t), P_{π_{j}}(j ≥ t + 1)) t = 1, 2, …, n útrendszereken el lehessen vezetni az igényeket, a kapacitásfeltétel megsértése nélkül, illetve eldönteni, hogy létezik-e egyáltalán ilyen sorrend. Legyen a kezdeti és a végső útrendszer által használt kapacitás L_{0}, illetve

L_{n}, azaz L_{0} = ∑_{i=1}^{n} d_{i}p_{i} és L_{n} = ∑_{i=1}^{n} d_{i}q_{i}, továbbá legyen

v_{i} = d_{i}(q_{i} − p_{i}).  (1)

A keresett π permutációra tehát

L_{0} + ∑_{i=1}^{t} v_{π_{i}} ≤ c, 1 ≤ t ≤ n.

Általában ilyen π permutáció nyilván nem létezik. Viszont ha feltesszük, hogy az igények mind P mind Q útrendszereken való elvezetésekor egyaránt van a rendszerben elég nagy szabad kapacitás, akkor már állítható, hogy létezik megfelelő sorrendezés. Amennyiben

c(e) ≥ L_{0}(e) + L_{n}(e) ∀e ∈ E,

akkor

∑_{i=1}^{n} d_{i}p_{i} + ∑_{i=1}^{n} d_{i}q_{i} = L_{0} + L_{n} ≤ c,

így tetszőleges sorrend mentén átpakolhatók az utak, hisz mindkét útrendszer befér együtt is a kapacitásba, tehát az átpakolásokkal kapott összes részrendszer is. A továbbakban feltesszük, hogy L_{0} = L_{n}, jelöljük ezt L-lel, ami nem lényeges megszorítás, viszont egyszerűbb és átláthatóbb képleteket eredményez. A dolgozat célja feltárni, hogy a kapacitásra milyen alsó becslésnek kell teljesülni (a triviálisan szükséges alsó becslés) L és (a triviálisan elégséges) 2L között, az átpakolás létezéséhez illetve algoritmikus előálltásához. Látni fogjuk, hogy bizonyos esetekben a L alsó becslést alig túllépő kapacitás is elég. További cél az RSP-feladat rokonait vizsgálni az ütemezési és diszkrepancia feladatok közt.

Tudjuk, hogy a hálózatokban útelvezetésekkel kapcsolatban felmerülő feladatok között nincsenek kevesen az NP-teljesek, s nem meglepő, hogy az RSP is NP-teljes. Elsőre viszont talán meglepően hangzik a következő tétel.

Tétel 3.1. Az útátpakolási feladat a 2 élből álló gyűrűn NP-teljes.

Proof. Vegyük egy inputját a partícós problémának, nemnegatív egészeket b_{i}, i ∈ [k]. A kérdés, hogy a {b_{i} : i ∈ [k]} halmazhoz létezik-e S ⊂ [k] halmaz, amire ∑_{i∈S} b_{i} = ∑_{i∈[k]\S} b_{i}.

Jól ismert, hogy ez NP-teljes. Tekintsünk ehhez egy gyűrűt 2 éllel, legyenek ezek e és f,

és egy RSP-feladat, P_{i} = {e}, d_{i} = b_{i}, i ∈ [k], P_{k+1} = {f}, d_{k+1} = 1 2 ∑_{i∈[k]} b_{i}, Q_{i} = {f},

i ∈ [k], Q_{k+1} = {e}, c(e) = c(f) = ∑_{i∈[k]} b_{i}. Egy megengedett sorrendezés megadja a

partíciós problémának egy megoldását, és fordítva.

A dolgozat folyamán az RSP vizsgálatakor nem fogjuk kihasználni az utak és a gráf strukturális tulajdonságait, csak a ritkasági tulajdonságokat. Így általánosabb feladatot fogunk vizsgálni, melyben nem tesszük fel, hogy a vektorok utak incidenciavektoraiból származnak.

CVS1. Adott egy nullaösszegű vektorhalmaz, z_{1}, z_{2}, …, z_{k} ∈ ℝ^{m}, ∑_{i=1}^{k} z_{i} = 0, és egy

korlát D ∈ ℝ^{m}. A kérdés, hogy létezik-e olyan π permutéció, melyre

max_{1≤t≤k} ∑_{i=1}^{t} z_{π_{i}} ≤ D.

Tétel 3.2. A CVS1 NP-tejes.

Proof. Nyilván NP-beli, megmutatjuk hogy a SAT polinomiálisan visszavezethető rá. Vegyük a SAT egy inputját, ⋀_{j∈[m]} C_{j}, x_{i}, i ∈ [k] változókkal, ahol C_{j} = ⋁_{i∈A_{j}} x_{i}∨ ⋁_{i∈B_{j}} ¬x_{i}.

Feltehető, hogy |A_{j}| + |B_{j}| ≥ 2, j ∈ [m], hisz a többi klóz a benne szereplő egyetlen változó értékével elhagyható. Egy x_{i} változóra vegyünk egy v_{i} oszlopvektort, ¬x_{i}-hez pedig egy u_{i} vektort. Kell még további 3 vektor, y_{1}, y_{2} és z. Minden C_{j} klózra definiáljuk egy sorát a M = (v_{1}, v_{2}, …, v_{k}, y_{1}, u_{1}, u_{2}, …, u_{k}, y_{2}, z) mátrixnak, melyet a (C_{j}) felső indexszel látunk el, minden változóra 2 sort, (j1) és (j2) indexekkel, és extra sort (0)-val. Ezen mátrix oszlopai fogják a CVS1 vektorait alkotni.

Az x_{j} változóhoz rendelt (j1) sorban álljon 4 nemnulla elem, v_{j}^{(j1)} = −1, u_{j}^{(j1)} = −1, y_{1}^{(j1)} = 1, y_{2}^{(j1)} = 1, és a korlát D^{(j1)} = 0; a (j2) sorra pedig v_{j}^{(j2)} = 1, u_{j}^{(j2)} = 1, y_{1}^{(j2)} = −1, y_{2}^{(j2)} = −1, és a korlát D^{(j2)} = 1; az extra sor (0) pedig y_{1}^{(0)} = −1, y_{2}^{(0)} = −1, z^{(0)} = 2, a korlát D^{(0)} = 0.

Ezen definíciók alapján egy megengedett π permutáció a következőképpen épül fel: π = (E_{1}, F_{1}, E_{2}, F_{2}, h), ahol |E_{1}| = |E_{2}| = k, v_{i} ∈ E_{1} ⇔ u_{i} ∈ E_{2}, |F_{1}| = |F_{2}| = 1, az egyelemű halmazok y_{1} és y_{2} (vagy y_{2} és y_{1}), az utolsó pedig h.

A C_{j} = ⋁_{i∈A_{j}} x_{i} ∨ ⋁_{i∈B_{j}} ¬x_{i} klózra vegyünk egy sort, ahol v_{i}^{(C_{j})} = −1 ⇔ i ∈ A_{j},

u_{i}^{(C_{j})} = −1 ⇔ i ∈ B_{j}, y_{1}^{(C_{j})} = 1, y_{2}^{(C_{j})} = 1, z^{(C_{j})} = |A_{j}| + |B_{j}| − 2 (biztosítani a nullaösszegűséget), és egy korlátot D^{(C_{j})} = 0. A többi elem 0.

Tekintsük most a (C_{j}) sort. Amennyiben π megengedett, lennie kell legalább egy −1 elemnek az E_{1}-ben. Ezzel definiálható π alapján az x_{j} változó értéke, igaznak, ha u_{j} ∈ E_{1}, és hamisnak különben. Ez jó definíció lesz.

Másrészt, definiáljunk egy permutációt a változók értékeiből, ha adott a SAT-formula egy kielégítése. Ezen esetben legyen a permutáció a fenti alakú, π = (E_{1}, F_{1}, E_{2}, F_{2}, h), az igaz változóknak megfelelő vektorokat tegyük E_{1}-be, a többit E_{2}-be.

A későbbi CVS-feladat a részletösszegek normában való korlátozásáról fog szólni, innen a hasonló elnevezés.

4 Korlátos vektorösszegzés és diszkrepanciák

Most definiálunk három feladatot, később pedig megmutatjuk, hogy milyen kapcsolat áll fenn köztük, s akkor az is kiderül majd, hogy hogyan jelenthetnek segítséget az útátpakolási probléma megoldásánál.

Definíció 4.1. Tekintsük az (1, 2, …, n) sorozatnak egy π = (π_{1}, π_{2}, …, π_{n}) permutációját, és egy z_{1}, z_{2}, …, z_{n} ∈ ℝ^{m} vektorhalmazt. Összegezzük ezen vektorokat a π szerinti

sorrendben. Kössük össze az így kapott 0, z_{π}^{1}, z_{π}^{2}, …, z_{π}^{n} pontokat, ahol z_{π}^{k} = ∑_{j=1}^{k} z_{π_{j}}.

Az így kapott töröttvonalat a vektorrendszernek a π permutációhoz tartozó összegzési trajektóriájának nezezzük.

Korlátos vektorösszegzési feladat. Az angol elnevezés (compact vector summation) alapján ezt gyakran CVS-nek fogjuk rövidíteni. Legyen s egy norma ℝ^{m}-e, és

B = {z_{1}, z_{2}, …, z_{n}} ⊂ ℝ^{m} egy vektorhalmaz, melyre ∑_{i=1}^{n} z_{i} = 0, és ∥z_{i}∥_{s} ≤ 1, ahol

i ∈ [n], magyarul B ∈ B_{n,s,m}^{0}. A feladat keresni egy olyan π permutációt, hogy a B vektorrendszer π-hez tartozó összegzési trajektóriájának minden pontja legyen az nullához s-ben. Célunk tehát olyan π keresése, mely minimalizálja a

φ_{s}(B, π) = max_{1≤t≤n} ∥∑_{i=1}^{t} z_{π_{i}} ∥_{s}

függvényt. Legyen a minimum

φ_{s}(B) = min_{π} φ_{s}(B, π).

Vezessük be továbbá a

φ_{s}(m) = sup_{n} sup_{B∈B_{n,s,m}^{0}} φ_{s}(B)

jelölést. (Itt több függvényre is használjuk ugyanazt a jelölést, ilyen később is lesz, de az argumentum típusa mindig meg fogja határozni, hogy miről is van szó.) Eddig semmi nem garantálja hogy az itt vizsgált φ_{s}(m) véges lenne. Ezt Steinitz bebizonyította, és a későbbiekben mi is látni fogjuk igazolását, sőt algoritmikus becsléseket fogunk látni, azaz a φ_{s}(m) felső becsléséhez elő is fogunk állítani algoritmikusan megfelelő sorrendet. Nevezzük φ_{s}(m)-et az irodalomnak megfelelően Steinitz-függvénynek.

Térjünk most vissza egy kicsit az eredeti mederbe. Az RSP-nél olyan sorrendet kerestünk hogy az összegzési trajektória minden koordinátafüggvénye felülről korlátos, aminek egy természetes megfelelője a CVS egy ℓ_{∞}-szerű normával vett esete, mely egy kicsit többet követel, így alulról való korlátozást is koordinátánként. Látni fogjuk, hogy ennek ellenére az RSP megoldása során gyümölcsözőek lesznek a CVS-en végzett vizsgálataink. A CVS vizsgálata azért is lesz hasznos, mert a szimmetrikus esetben sokkal könnyebben tudunk az igazsághoz közeli becsléseket adni.

Mutatunk egy másik feladatot, ahol a CVS szintén felmerül, bár még ennél is kevésbé szigorúan.

Hogy egy kicsit szemléletesebb legyen, a feladatot egy hétköznapi alkalmazással fogalmazzuk meg.

VCP-feladat (volume calendar planning). Bővebben olvashatunk ezen feladatokról [Se1, Se2]-ben, és Sevastyanov további cikkeiben. Vegyünk egy vállalatot, amelynek az éves terve n tételt tartalmaz, mind egy-egy m-dimenziós vektorral írható le:

a_{j} = (a_{1}^{j}, a_{2}^{j}, …, a_{m}^{j})^{T}, j ∈ [n], A = {a_{j} : j ∈ [n]}, a = ∑_{i=1}^{n} a_{i}, és ∥a_{j}∥_{s} ≤ 1, azaz

A ∈ B_{n,s,m}. (A szemléltetés persze csak nemnegatív vektorokra értelmes, a feladatot viszont nem csak nemnegatív rendszerekre definiáljuk.) A cél az éves tervet r részre osztani a lehető legegyenletesebben. Jelölje a partíciót S = {N_{1}, N_{2}, …, N_{r}}, ∪N_{i} = [n], N_{i} ∩ N_{j} = ∅, ha i ≠ j. Az egyenletességet nyilván többféle célfüggvénnyel mérhetjük, vegyük egyelőre a következőeket:

L_{s}^{1}(A, S) = max_{p,q} ∥ ∑_{j∈N_{p}} a_{j} − ∑_{j∈N_{q}} a_{j}∥_{s} → min

vagy

L_{s}^{2}(A, S) = max_{p} ∥ ∑_{j∈N_{p}} a_{j} − a ; r∥_{s} → min .

És legyen L_{s}^{i}(A) = min_{S} L_{s}^{1}(A, S). Definiáljuk továbbá a

η_{s}^{i}(r, m) = sup_{A∈B_{s,m},|A|<∞} L_{s}^{i}(A)

függvényeket, ahol i ∈ 1, 2. Később látni fogjuk, hogy ezek a szuprémumok végesek, melyeket a véges m-dimenziós vektorhalmazokon veszünk.

Kicsit megvizsgálva a partíció egyenletességét mérő két fenti függvényt, láthatjuk, hogy nem különböznek nagyon. Tekintsük ugyanis az S partícióban azokat az N_{p}, N_{q} részeket, ahol L_{s}^{1}(A, S) definíciójában a maximum felvétetik. Azonnal látszik, hogy

L_{s}^{1}(A, S) = ∥ ∑_{j∈N_{p}} a_{j} − ∑_{j∈N_{q}} a_{j}∥_{s} ≤ ∥ ∑_{j∈N_{p}} a_{j} − a ; r∥_{s} + ∥ ∑_{j∈N_{q}} a_{j} − a ; r∥_{s} ≤ 2L_{s}^{2}(A, S).

Másrészt, vegyük most azt a p-t melynél a maximum felvétetik L_{s}^{2}(A, S) definíciójában. Ekkor

L_{s}^{2}(A, S) = ∥ ∑_{j∈N_{p}} a_{j} − a ; r∥_{s} = ∥ ∑_{1≤q≤r} 1 ; r ( ∑_{j∈N_{p}} a_{j} − ∑_{j∈N_{q}} a_{j})∥_{s} ≤

≤ 1 ; r ∑_{1≤q≤r} ∥( ∑_{j∈N_{p}} a_{j} − ∑_{j∈N_{q}} a_{j})∥_{s} ≤ r − 1 ; rL_{s}^{1}(A, S).

Ezt az előző eredménnyel kombinálva kapjuk, hogy

r ; r − 1L_{s}^{2}(A) ≤ L_{s}^{1}(A) ≤ 2L_{s}^{2}(A),

illetve

r ; r − 1η_{s}^{2}(r, m) ≤ η_{s}^{1}(r, m) ≤ 2η_{s}^{2}(r, m).

(r=2 esetben tehát L_{s}^{1}(A, S) = 2L_{s}^{2}(A, S), így a két célfüggvény által meghatározott optimalizálási feladat ekvivalens.) Újabb interpretációja lehet a VCP-nek egy olyan ütemezési feladat, ahol a j ∈ [n] munkadarab megmunkálandó az 1, 2, …, k, …, m sorszámozású gépeken, a j munkadarab k. gépen vett megmunkálási ideje a_{k}^{j}, továbbá adott r alternatív brigád, melyek mindegyike redelkezik az m gép mindegyikével. A feladat szétosztani a j ∈ [n] munkákat az egyes brigádok közt úgy, hogy a befelyezési idő minimális legyen. A VCP-feladatban az s = ℓ_{∞} normát választva a kívánt ütemezési faladatot kapjuk

F (S) = max_{p} max_{k∈[m]} ∑_{j∈N_{p}} a_{k}^{j} → min

célfüggvénnyel. (Ebben a modellben egy munkadarabon egyszerre több gépen is végezhetnek részfeladatokat, ami nem a legszokásosabb feltétel az ütemezési feladatokban.)

Miért jelent a CVS segítséget a VCP megoldásánál. Tegyük fel, hogy a VCP inputjában adott {a_{j}} vektorok egy π permutációhoz tartozó trajektóriája minden pontja

közel halad a {λa : λ ∈ [0, 1]} szakaszhoz, ahol –emlékeztetőül– a = ∑_{i=1}^{n} a_{i} volt. Ekkor a

trajektóriát körülbelül egyenlő részekre oszthatjuk a fenti szakaszra merőlegesen a j ; r a, j = 1, 2, …, r − 1 pontokban emelt síkokkal. Ez így persze nem túl pontos, nézzük meg hogy kicsit konkrétabban miről is van szó.

Legyen n_{1} = rt, ahol t = ⌈n ; r⌉, n′ = n + n_{1}. Készítsük most el az A′ = {a_{i} : i ∈ [n′]} vektorhalmazt, ahol az i ∈ [n] indexekre magtartjuk a régi vektorokat, és legyen a_{i} =

− a ; n_{1} különben. Erre a rendszerre persze ∑_{i=1}^{n′} a_{i} = 0. A CVS feladatban az (1, 2, …, n′)

egy π permutációjára

∥∑_{i=1}^{k} a_{π_{i}} ∥_{s} ≤ φ_{s}(A′, π)

ahol k ∈ [n′].

Keressünk most 0 = k_{0} < k_{1} < ⋯ < k_{r} = n′ indexeket, hogy minden I_{p} = {π_{i} : k_{p−1} < i ≤ k_{p}} pontosan t darab π_{i} > n, azaz általunk hozzáadott indexet tartalmaz. Ekkor már legyárthatjuk a kívánt partíciót. Legyen N_{p} = I_{p}∩[n], S = {N_{1}, N_{2}, …, N_{r}}. Azt kapjuk tehát hogy

L_{s}^{2}(A, S) ≤ ∥ ∑_{i∈N_{p}} a_{i} − a ; r∥_{s} ≤ \begin{cases}φ_{s}(A′, π), & p ∈ \{1, r\}, \\ 2φ_{s}(A′, π), & p = 2, 3, …, r − 1, \end{cases}

illetve

L_{s}^{2}(A) ≤ φ_{s}(A′), ha r = 2,
L_{s}^{2}(A) ≤ 2φ_{s}(A′), ha r > 2.

Végsősoron a következőképpen foglalható össze a számolásunk.

Tétel 4.2.

η_{s}^{2}(2, m) ≤ φ_{s}(m),
η_{s}^{2}(r, m) ≤ 2φ_{s}(m), ∀r.

Ez az állítás nagyon hasznos lesz abban, hogy a Steinitz-függvényre alsó becslést adjunk, hisz a VCP-feladat egyszerűbb struktúrájából adódóan ott könnyebben fogunk tudni alsó becsléseket adni.

Az itt definiált partíciós probléma nekünk az r=2 esetben lesz a legfontosabb. Most bár csak átfogalmazásról van szó, definiáljuk egy kicsit másként is ezt a feladatot r=2-re. A következő A. Dvoretzky által 1963-ban megfogalmazott probléma a 7th Symposium of AMS in Pure Mathematics megoldatlan problémáinak listáján szerepel.

Keressük a

ν_{s}(m) = sup min ∥ ∑_{i∈[|A|]} ε_{i}a_{i}∥_{s}

függvény értékeit, ahol a szuprémum az összes véges A ⊂ B_{s,m} rendszerre, a minimum pedig az ε_{i} ∈ {−1, 1}, i ∈ [|A|] rendszerekre megy. Bevezetünk még néhány diszkrepanciaelméletben szokásos jelölést, hogy lássuk mihez is kapcsolódik ez a függvény.

Halmazrendszer diszkrepanciája, mátrix diszkrepanciája, és diszkrepancia normában. Először halmazrendszer diszkrepanciáját fogjuk definiálni. Legyen F = {F_{1}, F_{2}, …, F_{m}} ∈ F_{n,m} az [n] alaphalmazon egy m halmazból álló halmazrendszer. Az ε = (ε_{1}, ε_{2}, …, ε_{n}) ∈ {−1, 1}^{n} „szinezés” mellett az F diszkrepanciája

disc(F, ε) = max_{j∈[m]} |∑_{i∈F_{j}} ε_{i}| ,

ami tehát azt méri, hogy az ε szinezés mennyire egyenletesen vágja ketté a halmazrendszer elemeit. Az F halmazrendszer diszkrepanciája pedig

disc(F) = min_{ε∈{−1,1}^{n}} disc(F, ε).

A diszkrepanciát néha a fenti felének szokták definiálni, mint például a [LSV] cikkben.

Legyen most A egy olyan m × n-es mátrix, melynek minden eleme a [−1, 1] intervallumba esik, oszlopai pedig az a_{1}, a_{2}, …, a_{n} ∈ ℝ^{m} vektorok. Ekkor az A mátrix diszkrepanciája a fentihez teljesen hasonlóan definiálható az ε ∈ {−1, 1}^{n} szinezésnél,

disc(A, ε) = ∥∑_{i=1}^{n} ε_{i}a_{i}∥_{ℓ_{∞}} ,

illetve az A mátrix diszkrepanciája

disc(A) = min_{ε∈{−1,1}^{n}} disc(A, ε).

A közös jelölés, illetve a halmazrendszer diszkrepanciájának mátrixra való általánosításának az a magyarázata, hogy az F halmazredszer és A incidenciamátrixának diszkrepanciája a fenti két értelemben megegyezik, így a halmazrendszer diszkrepanciája speciális esete a mátrix diszkrepanciájának. Hogy eljussunk a Dvoretzky által kérdezett függvényhez, ezt a fogalmat még tovább fogjuk általánosítani.

Legyen s egy norma ℝ^{m}-en, A = (a_{1}, a_{2}, …, a_{n}) ∈ B_{n,s,m}, és ε ∈ {−1, 1}^{n}-re

disc_{s}(A, ε) = ∥∑_{i=1}^{n} ε_{i}a_{i}∥_{s} ,

illetve

disc_{s}(A) = min_{ε∈{−1,1}^{n}} disc_{s}(A, ε),

disc_{s}(n, m) = sup_{A∈B_{n,s,m}} disc_{s}(A),

disc_{s}(m) = sup_{n} disc_{s}(n, m).

Tehát Dvoretzky ezen utolsó függvény viselkedésére volt kiváncsi. Látható az is, hogy s = ℓ_{∞} normával az eredeti diszkrepanciafogalmat kapjuk vissza.

Azonnal látszik, hogy a VCP feladat r = 2-re pontosan ezt a Dvoretzky-féle feladatot adja, hiszen legyen S = {N_{1}, N_{2}} az a partíció, melyre N_{1} = {i : ε_{i} = +1}, N_{2} = {i : ε_{i} = −1}. És így

η_{s}^{1}(2, m) = disc_{s}(m).

Most bemutatjuk a diszkrepancia egy dinamikus változatát, aminél viszont a sorrendezési feladat korlátja lesz kisebb.

Dinamikus diszkrepancia. Néha talán előfordul majd, hogy ezt a feladatot dinamikus előjelezésnek nevezzük, vagy DVB-nek (Dynamic Vector Balancing), azért mert az irodalomban sokféle néven felbukkan. Adott egy A = {a_{1}, a_{2}, …, a_{n}} ⊂ B_{s,m} véges vektorhalmaz. Keressük azt az ε = (ε_{1}, ε_{2}, …, ε_{n}) ∈ {−1, +1}^{n} előjelezést, melyre

μ_{s}(A, ε) = max_{1≤t≤n} ∥∑_{i=1}^{t} ε_{i}a_{i}∥_{s}

minimális, azaz minden előjelezett részletösszeg „kicsi”. A minimumot jelölje μ_{s}(A), illetve legyen

μ_{s}(n, m) = sup_{A∈B_{n,s,m}} μ_{s}(A),

μ_{s}(m) = sup_{n} μ_{s}(n, m).

A következő lemma jól illusztrálja, hogy miért is nehezebb ez a feladat, megadva a korlátok közti egyenlőtlenséget.

Lemma 4.3. (Chobanyan lemmája, [BeS, p. 1421.])

Legyenek z_{1}, z_{2}, …, z_{n} ∈ ℝ^{m}, ∑_{k=1}^{n} z_{k} = 0, és ∥·∥ egy tetszőleges norma ℝ^{m} − en. Te-

gyük fel, hogy az (1, 2, …, n) sorozat minden π = (π_{1}, π_{2}, …, π_{n}) permutációjára létezik ε_{1}^{π}, ε_{2}^{π}, …, ε_{n}^{π} ∈ {−1, +1} előjelezés, hogy

max_{1≤t≤n} ∥∑_{k=1}^{t} ε_{k}^{π}z_{π_{k}} ∥ ≤ A.

Ekkor van egy olyan ϱ = (ϱ_{1}, ϱ_{2}, …, ϱ_{n}) permutáció is, hogy

max_{1≤t≤n} ∥∑_{k=1}^{t} z_{ϱ_{k}} ∥ ≤ A.

Proof. Legyen

B = min_{π=(π_{1},π_{2},...,π_{n})} max_{1≤t≤n} ∥∑_{k=1}^{t} z_{π_{k}} ∥ .

Megmutatjuk, hogy B ≤ A. Legyen σ = (σ_{1}, σ_{2}, …, σ_{n}) az a permutáció, ahol a minimum felvétetik. A feltevés szerint van egy olyan ε_{1}^{σ}, ε_{2}^{σ}, …, ε_{n}^{σ} ∈ {−1, +1} előjelezés, hogy

max_{1≤t≤n} ∥∑_{k=1}^{t} ε_{k}^{σ}z_{σ_{k}} ∥ ≤ A.

Legyen M^{+} = {k ∈ [n] : ε_{k}^{σ} = +1}, és M^{−} = {k ∈ [n] : ε_{k}^{σ} = −1}. Ekkor

∑_{k=1}^{t} z_{σ_{k}} + ∑_{k=1}^{t} ε_{k}^{σ}z_{σ_{k}} = 2 ∑_{k∈M^{+},1≤k≤t} z_{σ_{k}},

és

∑_{k=1}^{t} z_{σ_{k}} − ∑_{k=1}^{t} ε_{k}^{σ}z_{σ_{k}} = 2 ∑_{k∈M^{−},1≤k≤t} z_{σ_{k}}.

Így

∥ ∑_{k∈M^{+},1≤k≤t} z_{σ_{k}} ∥ ≤ A + B ; 2 ,  illetve  ∥ ∑_{k∈M^{−},1≤k≤t} z_{σ_{k}} ∥ ≤ A + B ; 2 .

Az M^{+} = {p_{1} < p_{2} < ⋯ < p_{r}} és M^{−} = {q_{1} < q_{2} < ⋯ < q_{s}} jelöléssel definiálhajuk a

ϱ = (p_{1}, p_{2}, …, p_{r}, q_{s}, q_{s−1}, …, q_{1}) = (ϱ_{1}, ϱ_{2}, …, ϱ_{n})

permutációt. Ekkor ∑_{k=1}^{n} z_{k} = 0,

max_{1≤t≤n} ∥∑_{k=1}^{t} z_{ϱ_{k}} ∥ ≤ A + B ; 2 .

Minthogy B volt a minimum, B ≤ A+B ; 2 , és így B ≤ A.

Valójában Chobanyan lemmája egy közelítő algoritmust is ad a CVS feladat megoldásához. Az előző bizonyításban alkalmazott lépést kell iterálni, ha ismerünk egy algoritmust, amely megoldja a DVB-t. Pontosabban...

Lemma 4.4. Legyen z_{1}, z_{2}, …, z_{n} ∈ ℝ^{d} ahol ∑_{k=1}^{n} z_{k} = 0. Tegyük fel, hogy van egy A

algoritmusunk, amely az (1, 2, …, n) sorozat π = (π_{1}, π_{2}, …, π_{n}) permutációjára elő tud állítani egy ε_{1}^{π}, ε_{2}^{π}, …, ε_{n}^{π} ∈ {−1, +1} előjelezést, hogy

max_{1≤t≤n} ∥∑_{k=1}^{t} ε_{k}^{π}z_{π_{k}} ∥ ≤ D,

továbbá adott egy π^{(0)} = (π_{1}^{(0)}, π_{2}^{(0)}, …, π_{n}^{(0)}) permutáció, amire

max_{1≤t≤n} ∥∑_{k=1}^{t} z_{π_{k}^{(0)}} ∥ ≤ E.

Ekkor az A algoritmus s-szeri alkalmazásával elő tudunk állítani egy π^{(s)} = (π_{1}^{(s)}, π_{2}^{(s)}, …, π_{n}^{(s)}) permutációt, amire

max_{1≤t≤n} ∥∑_{k=1}^{t} z_{π_{k}^{(s)}} ∥ ≤ D + E − D ; 2^{s} .

Ezen a ponton érdemes egy tételben összefoglalni azokat az egyszerű egyenlőtlenségeket, amiket a három feladat kapcsolatára kicsikartunk.

Tétel 4.5. Legyen Z = {z_{1}, z_{2}, …, z_{n}} ⊂ ℝ^{m}, ahol ∑_{i=1}^{n} z_{i} = 0. Ekkor

1 2disc_{s}(Z) ≤ φ_{s}(Z) ≤ max_{π} μ_{s} ({z_{π_{1}}, z_{π_{2}}, …, z_{π_{n}}}) ,

ahol a jobboldali maximum az (1, 2, …, n) sorozat összes π permutációjára megy, illetve

1 2disc_{s}(m) ≤ φ_{s}(m) ≤ μ_{s}(m).

Proof. A bizonyításhoz, hogy egy kicsit jobban lássunk a jelölések tengerében,

disc_{s}(Z) = L_{s}^{1}(Z) = 2L_{s}^{2}(Z) ≤ 2φ_{s}(Z)

adja az alsó becslést, a felső becslést pedig épp most láttuk.

Ezek szerint μ_{s}(m) végességének igazolásával igazolnánk az eddig definiált összes függvény végességét, beleértve ebbe φ_{s}(m), η_{s}^{1}(r, m), η_{s}^{2}(r, m), és disc_{s}(m) végességét. Ezt a feladatot hagyjuk későbbre. Kezdjük a sort φ_{s}(m) végességének igazolásával.

4.1 A Steinitz-függvény végessége

Most belátjuk a Steinitz-függvény végességét, sőt az s normától független korlátot adunk φ_{s}(m)-re, egy olyan bizonyítással, mely algoritmust is ad ilyen korláttal rendelkező permutáció előállítására.

Tétel 4.6. (Grinberg, Sevastyanov)

φ_{s}(m) ≤ m.

Proof. Vegyünk egy {z_{1}, z_{2}, … z_{n}} ∈ B_{n,s,m}^{0} inputot, és az egyszerűség kedvéért hagyuk el az s jelölést. Feltehető, hogy n > m, különben tetszőleges sorrenddel készen vagyunk. A permutációt a végéről visszafelé haladva fogjuk legyártani, mégpedig indukcióval megkonstruálunk egy N_{m} ⊂ N_{m+1} ⊂ ⋯ ⊂ N_{n} = [n] indexhalmaz sorozatot, és λ_{j} : N_{j} → ℝ számokat úgy, hogy |N_{j}| = j, 0 ≤ λ_{j}(i) ≤ 1, (j ∈ [n], i ∈ N_{j}) és

∑_{i∈N_{j}} λ_{j}(i) = j − m  (2)
∑_{i∈N_{j}} λ_{j}(i)z_{i} = 0  (3)

j = n esetén legyen N_{n} = [n] és λ_{n}(i) = n − m ; n. Minthogy ∑_{i=1}^{n} z_{i} = 0, ez kielégíti a

feltételeket. Ha már j + 1-re készen vagyunk, akkor tekintsük a

λ(i) ≤ 1 i ∈ N_{j+1}  (4)
λ(i) ≥ 0 i ∈ N_{j+1}  (5)
∑_{i∈N_{j+1}} λ(i) = j − m  (6)
∑_{i∈N_{j+1}} λ(i)z_{i} = 0  (7)

egyenlőtlenségrendszert, ahol a változók λ(i), i ∈ N_{j+1}. Ennek van megoldása, például

λ(i) = j − m ; j + 1 − mλ_{j+1}(i).

Ekkor van olyan λ′(i), i ∈ N_{j+1} megoldás is, amelyben az egyik változó nulla, mondjuk λ′(k) = 0 valamely k ∈ N_{j+1}-re. Vegyünk egyszerűen egy bázis megoldást. Tegyük fel, hogy nincs köztük 0. Ekkor a rendszerben rangnyi sok feltétel egyenlőséggel teljesül, azaz legalább (j + 1) − (m + 1) = j − m darab λ′(i) 0 vagy 1, azaz 1, mert 0 nincs, a többi pedig szigorúan pozitív. Ekkor ∑_{i∈N_{j+1}} λ′(i) > j − m. Ellentmondás.

Legyen most N_{j} = N_{j+1} \ {k}, és λ_{j}(i) = λ′(i), i ∈ N_{j}, amivel kész az indukció. Az N_{1}, N_{2}, …, N_{m−1} halmazokat pedig válasszuk tetszőlegesen, az |N_{j}| = j, N_{1} ⊂ N_{2} ⊂ … N_{m−1} ⊂ N_{m} feltétel mellett. A készülő permutációnk pedig π = (N_{1}, N_{2} \ N_{1}, N_{3} \ N_{2}, …, N_{n−1} \ N_{n−2}, N_{n} \ N_{n−1}) lesz.

Ha j ≤ m, akkor

∥∑_{i=1}^{j} z_{π_{i}} ∥ ≤ ∑_{i=1}^{j} ∥z_{π_{i}}∥ ≤ j ≤ m.

Ha pedig j > m, akkor

∥∑_{i=1}^{j} z_{π_{i}} ∥ = ∥ ∑_{i∈N_{j}} z_{i}∥ = ∥ ∑_{i∈N_{j}} z_{i} − ∑_{i∈N_{j}} λ_{j}(i)z_{i}∥ = ∥ ∑_{i∈N_{j}} (1 − λ_{j}(i)) z_{i}∥ ≤

≤ ∑_{i∈N_{j}} (1 − λ_{j}(i)) ∥z_{i}∥ ≤ ∑_{i∈N_{j}} (1 − λ_{j}(i)) = j − (j − m) = m.

A bizonyítás –mint láttuk–, kizárólag a vektorrendszer lineáris algebrai tulajdonságait, lineáris összefüggéseit használta, ezért is független az s-től. Bár ügyesen alkalmazva, a bizonyítás azon az egyszerű gondolaton alapul, hogy egy dimenziónál nagyobb elemszámú vektorrendszer lineárisan összefüggő, ennek segítségével ugyanis lehet egy tetszőleges megoldásból bázis megoldást készíteni.

Megjegyzés 4.7. A 4.6 tétel bizonyításában adott algoritmus futási ideje O(n^{2}m^{3})

Megjegyzés 4.8. Vegyük észre, hogy a 4.6 tétel bizonyításában a norma tulajdonságaiból csak a nemszimmetrikus félnorma tolajdonságait használtuk, azaz a háromszögegyenlőtlenséget, és azt, hogy a nemnegatív konstans kihozható a függvényből, így a tétel nemszimmetrikus félnormákra is igaz.

További általánosítása lehet a tételnek egy olyan változat, amelyben nem 0 összegű vektorrendszert tekintünk, ekkor viszont nem várhatjuk el, hogy minden részletösszeg kicsi legyen, azt viszont igen, hogy egy csőben haladjon a trajektória.

Tétel 4.9. (Grinberg, Sevastyanov)

Legyen t egy nemszimmertikus félnorma ℝ^{m}-en, és {z_{1}, z_{2}, … z_{n}} ∈ B_{t,m}. Ekkor létezik az (1, 2, …, n) sorozatnak egy olyan π = (π_{1}, π_{2}, …, π_{n}) permutációja, hogy j ≤ m esetén

∥∑_{i=1}^{j} z_{π_{i}} ∥_{t} ≤ j,

j > m-re pedig

∥∑_{i=1}^{j} z_{π_{i}} − j − m ; n ∑_{i=1}^{n} z_{i}∥_{t} ≤ m.

Egy ilyen trajektória a 4.6 tételben leírthoz hasonló módon polinomidőben meghatározható.

Felmerül a kérdés, hogy a φ_{s}(m)-re adott korlát vajon mennyire éles. Mindjárt látni fogjuk, hogy van olyan norma, ahol legalábbis a nagyságrendet tekintve éles. Láttuk korábban (4.2 tétel), hogy 1 2disc_{s}(m) ≤ φ_{s}(m). Legyen most s = ℓ_{1} és tekintsük a diszkrepanciafeladat inputjaként az E = {e_{1}, e_{2}, …, e_{m}} egységvektorokat, ahol e_{i}-ben pontosan egy helyen, mégpedig az i helyen áll 1, a többi helyen 0. Ekkor könnyen látszik, hogy tetszőleges ε ∈ {−1, +1}^{n} előjelezésre

disc_{ℓ_{1}}(E) = ∥∑_{j=1}^{n} ε_{j}e_{j}∥_{ℓ_{1}} = m,

tehát

φ_{ℓ_{1}}(m) ≥ m ; 2.

Tétel 4.10.

m ; 2 ≤ φ_{ℓ_{1}}(m) ≤ m.

Általában igazolható egy kicsit jobb korlát tetszőleges s normában, mégpedig φ_{s}(m) ≤ m − 1 + 1 ; m, ezt az eredményt azonban itt nem igazoljuk, további speciális eredmények összefoglalása található [Se1]-ben.

5 Diszkrepanciák és kerekítések

Korábban már definiáltunk néhány diszkrepanciát, most újabbak következnek. A jelöléseink talán nem a legelfogadottabbak, de mindig egyértelmű lesz, hogy miről van szó.

Lineáris diszkrepancia, lineáris diszkrepancia normában. Legyen s egy norma ℝ^{m}-en, A = (a_{1}, a_{2}, …, a_{n}) ∈ B_{n,s,m}, és p ∈ [−1, 1]^{n}. Ekkor ε ∈ {−1, 1}^{n}-re

lindisc_{s}(A, p, ε) = ∥∑_{i=1}^{n}(ε_{i} − p_{i})a_{i}∥_{s} ,

illetve az A mátrix lineáris diszkrepanciája

lindisc_{s}(A) = max_{p∈[−1,1]^{n}} min_{ε∈{−1,1}^{n}} lindisc_{s}(A, p, ε),

lindisc_{s}(n, m) = sup_{A∈B_{n,s,m}} lindisc_{s}(A),
lindisc_{s}(m) = sup_{n} lindisc_{s}(n, m).

Az s = ℓ_{∞} esetben a klasszikus lineáris diszkrepancia fogalmát kapjuk vissza. A következő fogalmak már nem lesznek ennyire fontosak vizsgálataink szempontjából, ám szemléletesebbé teszik ténykedésünket, így érthetőbb lesz a korábbi feladatok viselkedése is.

HB (Hypergraph balancing). Következőnek definiáljuk az Olson és Spencer, illetve Beck és Fiala által bevezetett „Hypergraph balancing” problémát. (Először Olson és Spencer vizsgálták r=2-re, majd Beck és Fiala kiterjesztették tetszőleges r-re.) Adott az [n] = {1, 2, … n} halmazon egy F = {F_{1}, F_{2}, …, F_{m}} halmazrendszer. Keresünk egy olyan S = {N_{1}, N_{2}, … N_{r}} partícióját az [n] alaphalmaznak, ami minimalizálja a

q(F, S) = max_{i,j,k} ||F_{i} ∩ N_{j}| − |F_{i} ∩ N_{k}||

funkcionált. A minimumot jelölje q(F). Legyen továbbá

η^{HB}(r, m) = sup_{n} max_{F} q(F).

Vegyük észre, hogy itt tulajdonképpen a VCP speciális esetéről van szó, ugyanis legyen s = ℓ_{∞} és válasszunk a VCP feladatban olyan a_{1}, a_{2}, …, a_{n} m-dimenziós vektorokat, hogy az általuk mint oszlopok által alkotott (a_{1}, a_{2}, …, a_{n}) mátrix az F incidenciamátrixa legyen, azaz a_{j} = (a_{1}^{j}, a_{2}^{j}, …, a_{m}^{j})^{T}, j ∈ [n] esetén

a_{i}^{j} = \begin{cases}1, & haj ∈ F_{i}, \\ 0, & különben. \end{cases} .

Ekkor

q(F, S) = max_{i,j,k} ||F_{i} ∩ N_{j}| − |F_{i} ∩ N_{k}|| = max_{j,k} max_{i} | ∑_{l∈N_{j}} a_{i}^{l} − ∑_{l∈N_{k}} a_{i}^{l}| =

= max_{j,k} ∥ ∑_{l∈N_{j}} a_{l} − ∑_{l∈N_{k}} a_{l}∥_{ℓ_{∞}} = L_{ℓ_{∞}}^{1}(A, S).

A következő probléma egy kicsit geometriaibb köntösbe öltözteti a diszkrepanciákat.

NV (nearest vertex). A korábban szerepelt, Dvoretzky által bevezetett vector balancing feladat általánosításaként fogalmazható meg egy paralelepipedonban egy a parelelepipedonbal levő ponthoz legközelebbi csúcsot kereső feladat. Legyen P (A) =

{∑_{i=1}^{n} α_{i}a_{i} : α_{i} ∈ [0, 1]} az A = {a_{1}, a_{2}, …, a_{n}} ⊂ B_{s,m} vektorhalmaz által generált

paralelepipedon, P̂(A) = {∑_{i=1}^{n} α_{i}a_{i} : α_{i} ∈ {0, 1}} pedig a csúcshalmaza. (Itt paralele-

pipedonnak hívunk minden itt definiált dolgot, függetlenül attól, hogy elfajul-e, vagy

sokkal több vektorral generáljuk, mint a dimenzió.) Vegyünk egy x = ∑_{i=1}^{n} λ_{i}a_{i} ∈ P (A)

pontot a paralelepipedonban. A feladat keresni egy y ∈ P̂(A) csúcsot, ami az s normában legközelebb van x-hez, azaz ∥x − y∥_{s} = min_{z∈P̂(A)} ∥x − z∥_{s}. Legfőbb vizsgálataink a következő függvényre fognak esni:

η_{s}^{NV} (n, m) = sup_{A} sup_{x∈P (A)} min_{y∈P̂(A)} ∥x − y∥_{s}.

Fontos speciális eset, amikor csak a középponthoz legközelebbi csúcsot keressük, azaz

x = ∑_{i=1}^{n} 1 2a_{i}.

Ekkor legyen

η̄_{s}^{NV} (n, m) = sup_{A} min_{y∈P̂(A)} ∥x − y∥_{s}.

Legyen δ = (δ_{1}, δ_{2}, …, δ_{n}) ∈ {0, 1}^{n}, és az általa meghatározott csúcs a paralelepi-

pedonban ∑_{i=1}^{n} δ_{i}a_{i}. S a csúcs középponttól való távolsága

∥∑_{i=1}^{n} 1 2a_{i} − ∑_{i=1}^{n} δ_{i}a_{i}∥_{s} = 1 2 ∥∑_{i=1}^{n} (1 − 2δ_{i}) a_{i}∥_{s} = 1 2 ∥∑_{i=1}^{n} ε_{i}a_{i}∥_{s} ,

ahol a δ által meghatározott csúcsnak az ε = (1 − 2δ_{1}, 1 − 2δ_{2}, …, 1 − 2δ_{n}) ∈ {−1, +1}^{n} előjelezés felel meg. Így

2η̄_{s}^{NV} (m) = disc_{s}(m),

tehát visszakaptuk a Dvoretzky által felvetett előjelezési problémát, illetve a VCP-t r = 2-re. (Ez utóbbi kettő ekvivalenciáját már láttuk.)

Hasonlóan lehet látni, hogy a HB r = 2-re hogyan speciális esete a NV-nek. Pusztán a szemléletesség kedvéért érdemes még egy sokadik alakban definiálni az eddigi ℓ_{∞} lineáris diszkrepancia egy speciális esetét.

IM (integer making). Beck és Fiala vizsgálták a következő „integer making” problémát. Adott egy F = {F_{1}, F_{2}, …, F_{m}} halmazrendszer, F_{i} ⊂ {1, 2, …, n}, és α = (α_{1}, α_{2}, …, α_{n})^{T} ∈ ℝ^{n}. A feladat keresni egy olyan ᾱ = (ᾱ_{1}, ᾱ_{2}, …, ᾱ_{n})^{T} ∈ ℝ^{n} egész vektort, melyre |α_{i} − ᾱ_{i}| < 1, és minimalizálja a

χ(F, α, ᾱ) = max_{F_{k}∈F} | ∑_{i∈F_{k}} α_{i} − ∑_{i∈F_{k}} ᾱ_{i}|

funkcionált. Másként fogalmazva az α vektor egy ᾱ kerekítését keressük, ahol a kerekítés jóságát az méri, hogy a halmazrendszer elemein a komponensek összege ne térjen el nagyon a kerekítettől. Ezen feladatokra nincs célunkban további jelöléseket bevezetni, a sok feladat definiíciója is csak a szemléletesség növelését célozta meg.

6 Diszkrepanciák néhány speciális ℓ_{p} normában

6.1 Általános becslések, és az ℓ_{1} norma speciális esete

Ebben a fejezetben a Dvoretzky által feltett kérdéssel fogunk foglalkozni néhány speciális normában. Azt már láttuk a 4.6 tétel következményeként, hogy a Dvoretzky-függvény disc_{s}(m) véges, hiszen

disc_{s}(m) ≤ 2φ_{s}(m) ≤ 2m.

Most mégis mutatunk egy közvetlen bizonyítást, ugyanis ennél jobb felső becslést fogunk kapni, mégpedig olyat, hogy van olyan norma, amiben ez az érték pontos.

Lemma 6.1. Legyenek z_{1}, z_{2}, …, z_{n} ∈ ℝ^{m} vektorok, p_{1}, p_{2}, …, p_{n} ∈ [−1, +1],

w = ∑_{i=1}^{n} p_{i}z_{i}. Ekkor léteznek olyan α_{1}, α_{2}, …, α_{n} ∈ [−1, +1], ∑_{i=1}^{n} α_{i}z_{i} = 0, hogy

|{i ∈ [n] : α_{i} ∈ (−1, 1)}| ≤ m.

A lemma alkalmazásával gyakran elég lesz olyan vektorrendszerek diszkrepanciáit vizsgálni, melyeknél legfeljebb annyi vektor van, mint dimenzió.

Proof. Vegyük azt az α_{1}, α_{2}, …, α_{n} ∈ [−1, +1] együtthatórendszert, melyre ∑_{i=1}^{n} α_{i}z_{i} =

w, A = {i ∈ [n] : α_{i} ∈ (−1, 1)} és |A| minimális.

Tegyük fel, hogy |{i ∈ [n] : i ∈ A| > m. A {z_{i} : i ∈ [n], α_{i} ∈ A} vektorok tehát lineárisan összefüggenek, ∑_{i∈A} β_{i}z_{i} = 0, ahol nem minden β_{i}, i ∈ A 0. Ekkor létezik olyan

λ > 0 szám, hogy α_{i} + λβ_{i} ∈ [−1, 1], és

|{i ∈ [n] : α_{i} + λβ_{i} ∈ (−1, 1)}| < |{i ∈ [n] : α_{i} ∈ (−1, 1)}|,

ami ellentmond |A| minimális választásának.

Ebből jobb felső becslés adódik a Dvoretzky-függvényre.

Tétel 6.2.

disc_{s}(n, m) ≤ min(n, m).

Proof. Legyen {z_{1}, z_{2}, …, z_{n}} ⊂ B_{s,m}. Az n ≤ m esetben készen vagyunk, legyen n > m. Ekkor vehetjük egy a 6.1 lemma szerinti együtthatókat p_{1} = p_{2} = ⋯ = p_{n} = 0val.

∑_{i=1}^{n} α_{i}z_{i} = 0, |{i ∈ [n] : α_{i} ∈ (−1, 1)}| ≤ m.

Ekkor válasszuk az ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, 1} előjelezést a következőképpen:

ε_{i} = \begin{cases}α_{i}, ha α_{i} ∈ \{−1, 1\}, \\ 1, ha 0 ≤ α_{i} < 1, \\ −1, ha − 1 < α_{i} < 0. \end{cases}

Ekkor

∥∑_{i=1}^{n} ε_{i}z_{i}∥_{s} = ∥∑_{i=1}^{n} ε_{i}z_{i} − ∑_{i=1}^{n} α_{i}z_{i}∥_{s} ≤ ∑_{i=1}^{n} |ε_{i} − α_{i}| ∥z_{i}∥_{s} ≤ m.

Láttuk korábban, hogy ℓ_{1} normában az e_{1}, e_{2}, …, e_{min(n,m)} egységvektorrendszer miatt min(n, m) ≤ disc_{ℓ_{1}}(m).

Tétel 6.3.

disc_{ℓ_{1}}(n, m) = min(n, m).

Analóg módon igazolható a következő tétel.

Tétel 6.4.

lindisc_{ℓ_{1}}(n, m) = min(n, m).

Ha a Dvoretzky-függvény nem konstans s-ben, akkor ezentúl nem tehetünk ilyen általános kijelentéseket, speciális normákra fogjuk vizsgálni.

6.2 Az ℓ_{2} norma szépen viselkedik

Legyen most s = ℓ_{2}. Ekkor ugyanúgy, mint az ℓ_{1} esetnél, megnézhetjük, hogy milyen alsó becslést tudunk levezetni az E = (e_{1}, e_{2}, …, e_{min(n,m)}) rendszerből. Minden kettévágás diszkrepanciája egyenlő, így azonnal adódik a következő állítás.

Lemma 6.5.

lindisc(n, m) ≥ disc_{ℓ_{2}}(n, m) ≥ √min(n, m).

A felső becsléshez valószínűségi módszert fogunk használni, bár van közvetlen, elemibb bizonyítás is. Szépsége miatt mégis az első illik ide jobban. Érdemes kimondani a kerekítési alakját is a tételnek.

Tétel 6.6. Legyen {z_{1}, z_{2}, …, z_{n}} ⊂ B_{ℓ_{2},m}, és α_{1}, α_{2}, …, α_{n} ∈ [0, 1], w = ∑_{i=1}^{n} α_{i}z_{i}.

Ekkor létezik olyan δ_{1}, δ_{2}, …, δ_{n} ∈ {0, 1} kerekítése az alfáknak, hogy

∥w − ∑_{i=1}^{n} δ_{i}z_{i}∥_{ℓ_{2}} ≤ \begin{matrix}√ & n \\ 2 \end{matrix}.

Tehát egy m-dimenziós euklideszi térben a z_{1}, z_{2}, …, z_{n} legfeljebb egységhosszúságú vektorokkal generált „paralelepipedonban” minden belső ponthoz van olyan „csúcs”,

mely legfeljebb \begin{matrix}√ & n \\ 2 \end{matrix} távolságra esik a ponttól. A Dvoretzky által kérdezett függvény pedig csak az iránt érdeklődik, hogy a középponttól milyen messze van a legközelebbi csúcs, és ennek veszi a szuprémumát minden megfelelő vektorrendszerrel által generált „paralelepipedonra”. Mi a következő tételt fogjuk bizonyítani, ami nyilvánvalóan ekvivalens a 6.6 tétellel.

Tétel 6.7. Legyen {z_{1}, z_{2}, …, z_{n}} ⊂ B_{ℓ_{2},m}, és α_{1}, α_{2}, …, α_{n} ∈ [−1, +1], w = ∑_{i=1}^{n} α_{i}z_{i}.

Ekkor léteznek olyan ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1}, hogy

∥w − ∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{2}} ≤ √n.

Proof. Egy véletlen kerekítést fogunk venni, legyenek a kerekített együtthatók E_{i}, i ∈ [n] független valószínűségi változók, mégpedig

ℙ (E_{i} = 1) = 1 + α_{i} ; 2 , ℙ (E_{i} = −1) = 1 − α_{i} ; 2

eloszlással. Ekkor

𝔼 ∥w − ∑_{i=1}^{n} Ez_{i}∥_{ℓ_{2}}^{2} = 𝔼 ∥∑_{i=1}^{n} α_{i}z_{i} − ∑_{i=1}^{n} E_{i}z_{i}∥_{ℓ_{2}}^{2} = 𝔼 ∥∑_{i=1}^{n} (α_{i} − E) z_{i}∥_{ℓ_{2}}^{2} =

= ∑_{i∈[n],j∈[n]} 𝔼 ((α_{i} − E_{i})(α_{j} − E_{j})) z_{i}^{T} z_{j} = ∑_{i∈[n]} 𝔼 ((α_{i} − E_{i})^{2}) ∥z_{i}∥_{ℓ_{2}}^{2} =

= ∑_{i∈[n]}(1 − α_{i}^{2})∥z_{i}∥_{ℓ_{2}}^{2} ≤ n.

Az utolsó egyenlőség 𝔼 ((α_{i} − E_{i})^{2}) = 1 − α_{i}^{2} felhasználásával látható. Tehát az E_{1}, E_{2}, …, E_{n} valószínűségi változóknak vannak olyan értékei, hogy a fenti normanégyzet legfeljebb n, és ezek az értékek jók lesznek.

Tétel 6.8.

disc_{ℓ_{2}}(n, m) = lindisc_{ℓ_{2}}(n, m) = √min(n, m).

Proof. Az alsó becslést láttuk a 6.5 lemmánál. A felső becsléshez tekintsük a z_{1}, z_{2}, …, z_{n} ∈ B_{s,m} vektorokat, és készítsük el a 6.1 lemma szerinti α_{1}, α_{2}, …, α_{n} ∈ [−1, +1] együtthatókat. Ekkor már csak olyan rendszer együtthatóit kell „kerekíteni”, melyek legfeljebb min(n, m)-en vannak. Ekkor a 6.7 tétel szerint „kikerekíthetjük” a még (−1, 1)-be eső együtthatókat, és a lineáris diszkrepancia a kívánt korlát alatt marad.

Korábbi vizsgálataink főként lineáris algebrai meggondolásokat használtak, s mindig látszott is, hogy a diszkrepanciára bizonyított felső becsléssel rendelkező előjelezést hogyan lehet algoritmikusan kiszámolni. Most azonban a valószínűségi módszer alkalmazásával csak az egzisztencia látszik.

Valójában teljesen elemi módon, determinisztikusan elő lehetett volna állítani a 6.7 tételben az előjelezést. Azért folyamodtunk a valószínűségi módszerhez, mert egyrészt magában is szép, másrészt hogy lássunk rá egy módszert, hogy bizonyos speciális esetekben az így kicsikart egzisztenciát hogyan lehet algoritmussá alakítani, erre ugyanis később még szükség lesz. Tehát egy ilyen egyszerű példán fogjuk bemutatni az Erdőstől és Spencertől származó feltételes valószínűségek módszerét.

Le kell tehát rögzítenünk a E_{i}, i ∈ [n] valószínűségi változók értékeit, úgy, hogy amikor már minden változó értékét lerögzítettük, akkor kicsi legyen a diszkrepancia. Egy valószínűségi változó lerögzítése annak felel meg, hogy egy feltételes valószínűségi mezőben dolgozunk tovább.

Gondoljunk meg néhány dolgot bizonyos feltételes valószínűségekről.

𝔼_{k}(ε_{1}, ε_{2}, …, ε_{k}) = 𝔼 (∥∑_{i=1}^{n} (α_{i} − E_{i}) z_{i}∥_{ℓ_{2}}^{2} | E_{1} = ε_{1}, E_{2} = ε_{2}, … E_{k} = ε_{k}) =

= 𝔼 (∥∑_{i=1}^{k} (α_{i} − ε_{i}) z_{i}∥_{ℓ_{2}}^{2} + ∥ ∑_{i=k+1}^{n} (α_{i} − E_{i}) z_{i}∥_{ℓ_{2}}^{2} +

+2 (∑_{i=1}^{k} (α_{i} − ε_{i}) z_{i})^{T} ( ∑_{i=k+1}^{n} (α_{i} − E_{i}) z_{i}) | E_{1} = ε_{1}, E_{2} = ε_{2}, … E_{k} = ε_{k}) =

= ∥∑_{i=1}^{k} (α_{i} − ε_{i}) z_{i}∥_{ℓ_{2}}^{2} + 𝔼 ∥ ∑_{i=k+1}^{n} (α_{i} − E_{i}) z_{i}∥_{ℓ_{2}}^{2} .

Végül a lemma bizonyításában látotthoz hasonlóan kapható, hogy

𝔼_{k}(ε_{1}, ε_{2}, …, ε_{k}) = ∥∑_{i=1}^{k} (α_{i} − ε_{i}) z_{i}∥_{ℓ_{2}}^{2} + ∑_{i=k+1}^{n} (1 − α_{i}^{2}) ∥z_{i}∥_{ℓ_{2}}^{2} .  (8)

A teljes várható érték tétele szerint

𝔼_{k}(ε_{1}, ε_{2}, …, ε_{k}) =

1 + α_{k+1} ; 2 𝔼_{k+1}(ε_{1}, ε_{2}, …, ε_{k}, 1) + 1 − α_{k+1} ; 2 𝔼_{k+1}(ε_{1}, ε_{2}, …, ε_{k}, 0), (9)

tehát

𝔼_{k}(ε_{1}, ε_{2}, …, ε_{k}) ≥ min (𝔼_{k+1}(ε_{1}, ε_{2}, …, ε_{k}, 1), 𝔼_{k+1}(ε_{1}, ε_{2}, …, ε_{k}, 0)) . (10)

Alkalmas ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} sorozat esetén tehát

\begin{matrix}√ & n \\ 2 \end{matrix} ≥ 𝔼_{0} ≥ 𝔼_{1}(ε_{1}) ≥ 𝔼_{2}(ε_{1}, ε_{2}) ≥ ⋯ ≥

≥ 𝔼_{n}(ε_{1}, ε_{2}, …, ε_{n}) = ∥∑_{i=1}^{n} (α_{i} − ε_{i}) z_{i}∥_{ℓ_{2}}^{2} . (11)

Láttuk (8)-ben, hogy a feltételes várható értékeket ki tudjuk számolni. Rögzítsük le a valószínűségi változók értékeit egymás után, egyenként. Egy E_{i} változó ε_{i}-re való lerögzítésére úgy tekintünk, hogy ezután az E_{i} = ε_{i} feltételnél vett feltételes valószínűségi mezőben dolgozunk tovább. A változókat minden egyes lépésben úgy fogjuk rögzíteni, hogy a fent számolt feltételes valószínűség ne nőjön. Ezt (10) szerint megtehetjük. Ezzel az eljárással egy döntési fa mentén algoritmikusan lerögzíthetjük a E_{i} i ∈ [n] valószínűségi változók értékeit, és megkapjuk a tételben kívánt kerekítést.

Nem lett volna az sem nagy ördöngősség, ha egyszerűen hasunkraütve vesszük a (8) súlyfüggvényt, és mindig ezen súlyfüggvényt minimalizálva lépünk a döntési fa mentén. Így azonban a valószínűségi módszer és a feltételes valószínűségek módszerének alkalmazásával meg is kaptuk ezt a súlyfüggvényt. Ez volt tehát a bemelegítő a valószínűségi módszer alkalmazásához.

6.3 ℓ_{∞} norma: a kellemetlen eset

Térjünk most rá az s = ℓ_{∞} eset vizsgálatára. Itt már sajnos nem lesz olyan szerencsénk mint eddig, az eddigiek közül ez a legnehezebb eset, és ennek az esetnek van az alkalmazásokban a legnagyobb szerepe. Az RSP-feladatban is egy ℓ_{∞}-szerű nemszimmetrikus félnormáról van szó.

Próbáljunk meg először alsó becslést adni, amihez csak olyan inputok kellenek, melyeknek bizonyítottan nagy az ℓ_{∞}-diszkrepanciája. Mutatunk ilyet. Tegyük fel, hogy létezik m rendű Hadamard-mátrix, legyen egy ilyen H_{m}. (Egy m × m-es H mátrixot Hadamard-mátrixnak nevezünk, minden eleme ±1 és H^{T} H = mI.) Legyenek a H_{m} mátrix oszlopai h_{1}, h_{1}, …, h_{m}. Vegyünk egy ε_{1}, ε_{2}, …, ε_{m} ∈ {−1, 1} előjelezést. A h_{i} vektorok páronként merőlegesek, így

∥∑_{i=1}^{m} ε_{i}h_{i}∥_{ℓ_{2}}^{2} = ∑_{i=1}^{m} ∥h_{i}∥_{ℓ_{2}}^{2} = m^{2}.

Az ℓ_{2} és ℓ_{∞} normák közti egyenlőtlenség miatt tehát

∥∑_{i=1}^{m} ε_{i}h_{i}∥_{ℓ_{∞}}^{2} ≥ 1 ; m ∥∑_{i=1}^{m} ε_{i}h_{i}∥_{ℓ_{2}}^{2} = 1 ; mm^{2} = m.

Lemma 6.9. Ha létezik m-rendű Hadamard-mátrix, akkor

disc_{ℓ_{∞}}(m) ≥ √m.

De vajon milyen m-ekre létezik Hadamard-mátrix? Azt lehet tudni, hogy m 1, 2, vagy osztható 4-gyel. Érdekes megoldatlan sejtés, hogy minden 4-gyel osztható m-re létezik-e. 1998-ban a legkisebb 4-gyel osztható rend, melyre nem volt ismert Hadamardmátrix, m=428 volt. 2-hatvány rendekre viszont nagyon egyszerű Hadamard-mátrixot gyártani, hiszen H_{1} = (1) Hadamard-mátrix, és ha H_{m} Hadamard-mátrix, akkor

H_{2m} = ( \begin{matrix}H_{m} & H_{m} \\ H_{m} & −H_{m} \end{matrix} )

is Hadamard-mátrix [SzT]. Ez mindenesetre elég ahhoz, hogy a Dvoretzky-függvényre ugyanolyan nagyságrendű alsó becslést kapjunk, mintha létezne Hadamard-mátrix megfelelő renddel.

Lemma 6.10.

disc_{ℓ_{∞}}(m) ≥ \begin{matrix}1 \\ √ & 2 \end{matrix}√m.

Felső becslést újra a valószínűségi módszer alkalmazásával fogunk adni, ehhez azonban szükségünk lesz egy egyenlőtlenségre, mely korlátos, független valószínűségi változók összegének a várható értéktől való nagy eltérésének valószínűségét becsli. A klasszikus exponenciális egyenlőtlenségek közül választunk egyet:

Tétel 6.11. ([Hoe], W. Hoeffding) Legyenek X_{1}, X_{2}, …, X_{n} független valószínűségi vál-

tozók, a_{i} ≤ X_{i} ≤ b_{i}, t > 0, S_{k} = ∑_{i=1}^{k} X_{i}, μ = 𝔼S_{n}. Ekkor

ℙ (S_{n} − μ > t) < exp (− 2t^{2} ; ∑_{i=1}^{n}(b_{i} − a_{i})^{2} ) .

Tétel 6.12. Legyen {z_{1}, z_{2}, …, z_{n}} ⊂ B_{ℓ_{∞},m}, és α_{1}, α_{2}, …, α_{n} ∈ [−1, 1], w = ∑_{i=1}^{n} α_{i}z_{i}.

Ekkor létezik olyan ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, 1}, hogy

∥w − ∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{∞}} ≤ √2n ln(2m),

amiből

lindisc_{ℓ_{∞}}(n, m) ≤ √2 min(n, m) ln(2m).  (12)

Proof. Egy véletlen előjelezést fogunk venni. Legyenek az együtthatók E_{i}, i ∈ [n] független valószínűségi változók, mégpedig

ℙ (E_{i} = 1) = 1 + α_{i} ; 2 , ℙ (E_{i} = −1) = 1 − α_{i} ; 2

eloszlással. Úgy csináltuk, hogy 𝔼E_{i} = α_{i} legyen. Ekkor

ℙ (∑_{i=1}^{n} E_{i}z_{j}^{i} − w_{j} > t) < exp (− t^{2} ; 2n) .

t = √2n ln(2m) választással a hiba valószínűsége, vagyis hogy van olyan koordináta, ahol a w megfelelő koordinátájától t-nél többel térünk el, legfeljebb

∑_{j=1}^{n} ℙ (∑_{i=1}^{m} E_{i}z_{j}^{i} − w_{j} > t) + ∑_{j=1}^{n} ℙ (∑_{i=1}^{m} E_{i}z_{j}^{i} − w_{j} < −t) < 2n exp (− t^{2} ; 2n) = 1,

tehát pozitív annak a valószínűsége, hogy egyik rossz esemény sem áll fenn, létezik jó előjelezés.

(12)-hez n ≤ m esetén készen vagyunk, különben vegyük egy 6.1 lemma szerinti együtthatókat. Ekkor már csk egy legfeljebb dimenziónyi vektoron kell megoldai egy kerekítési feladatot, tehát jogos a minimumképzés.

Később olyan előjelezést is képesek leszünk algoritmikusan készíteni, aminek az egzisztenciáját garantálta 6.12 tétel. A disc_{ℓ_{∞}}(m)-re adott alsó és felső becslés nagyságrendje azonban nem egyezik meg. A sejtés hosszú ideig az volt, hogy ezek közül az alsó becslés az éles, amit Spencernek 1984-ben sikerült bebizonyítani. A bizonyítás azonban lényegesen bonyolultabb mint a mi eddigi mesterkedéseink. A valószínűségi módszert kell benne kombinálni entrópia módszerrel és skatulyaelvvel. Emiatt máig nem ismert algoritmikus az általa garantált korlát elérésére.

Tétel 6.13. (Spencer, 1984, [Sp4])

disc_{ℓ_{∞}}(m, m) ≤ K√m,

ahol K abszolút konstans.

Megjegyzés 6.14. A tétel érvényes K = 5.32 konstanssal.

Hogy érzékeltessük, hogy a tétel csak a diszkrepancia aszimptotikus mérésében tölt be fontos szerepet, hasonlítsuk össze ezt az eredményt azzal, amit a valószínűségi módszer „egyszerű” alkalmazásával elértünk az 6.12 lemmában. Nyilvánvaló, hogy a K fenti értékével elég nagy m-re √2m ln(2m) ≥ K√m, azonban fordítva áll az egyenlőtlenség jóval több mint félmillióig.

Többször láttuk már, hogy a négyzetes esetet meg tudtuk oldani, s ennek a kerekítési változatát alkalmazva, –ami kicsit általánosabb–, a 6.1 lemma segítségével meg tudjuk oldani az általános esetet is. Most egy olyan megközelítést fogunk mutatni, ahol nem kell külön energiát fektetni a kerekítési változat megoldásába, hisz az következni fog az egyszerűbből, bár a konstans szorzó romlani fog.

Lemma 6.15. ([Sp4]) Legyen {z_{1}, z_{2}, …, z_{m}} ⊂ B_{ℓ_{∞},m}, és α_{1}, α_{2}, …, α_{m} ∈ [0, 1], w =

∑_{i=1}^{m} α_{i}z_{i}. Ekkor létezik olyan δ_{1}, δ_{2}, …, δ_{m} ∈ {0, 1} kerekítése az alfáknak, hogy

∥w − ∑_{i=1}^{m} δ_{i}z_{i}∥_{ℓ_{∞}} ≤ K√m

ahol K a Spencer tételében szereplő konstans, amiből

lindisc_{ℓ_{∞}}(m, m) ≤ 2K√m.

Proof. írjuk fel az α_{1}, α_{2}, …, α_{m} ∈ [0, 1] számokat kettes számrendszerben, s tegyük fel először, hogy véges sok jegyből állnak, s a kettedesvessző utáni utolsó jegy a T -edik. Legyen I azon i indexek halmaza, ahol α_{i} T -edik jegye 1. Ekkor a Spencer-tétel miatt létezik olyan ε ∈ {−1, +1}^{I}, hogy

∥∑_{i∈I} ε_{i}z_{i}∥_{ℓ_{∞}} ≤ K√m.

Legyen ekkor

α_{i}^{⋆} = \begin{cases}α_{i} + 2^{−T} , & ha ε_{i} = +1, \\ α_{i} − 2^{−T} , & ha ε_{i} = −1, \\ α_{i}, & ha i ∉ I. \end{cases} .

Az α_{i}^{⋆} együtthatóknak már csak legfeljebb T − 1 jegye van, és

∥∑_{i=1}^{n} α_{i}^{⋆}z_{i} − ∑_{i=1}^{n} α_{i}z_{i}∥_{ℓ_{∞}} ≤ 2^{−T} K√m.

Ezt az eljárást további T − 1-szer alkalmazva kapunk olyan ε ∈ {0, 1}^{n} együtthatózást, hogy

∥∑_{i=1}^{n} δ_{i}z_{i} − ∑_{i=1}^{n} α_{i}z_{i}∥_{ℓ_{∞}} ≤ ∑_{j=1}^{T} 2^{−j}K√m < K√m.

Tetszőleges α_{i} ∈ [0, 1], i ∈ [n] rendszerre pedig határátmenettel kapjuk megfelelő együtthatók létezését.

Tétel 6.16.

lindisc_{ℓ_{∞}}(m) = Θ(√m).

A legfontosabb normákra (ℓ_{1}, ℓ_{2}, ℓ_{∞}) már ismerjük a Dvoretzky-függvény nagyságrendjét. Érdemes még megnézni az ℓ_{p}, p ≥ 2 normákat.

Legyen H_{m} m-edrendű Hadamardmátrix, és a korábbi jelöléssel összhangban az oszlopai h_{1}, h_{2}, …, h_{m}. Ekkor a normák közti egyenlőtlenségeket használva

∥∑_{i=1}^{n} ε_{i} \begin{matrix}h_{i} \\ ^{p} & √m \end{matrix}∥_{ℓ_{p}} ≥ m^{1 ; q − 1 2} ∥∑_{i=1}^{n} ε_{i} \begin{matrix}h_{i} \\ ^{p} & √m \end{matrix}∥_{ℓ_{2}} = m^{1 ; q − 1 2} m^{1 2 − 1 ; q} ∥∑_{i=1}^{n} ε_{i} \begin{matrix}h_{i} \\ ^{2} & √m \end{matrix}∥_{ℓ_{2}} = √m.

Lemma 6.17. Ha létezik m-rendű Hadamard-mátrix, p ≥ 2, akkor

disc_{ℓ_{p}}(m) ≥ √m.

Másrészt az e_{1}, e_{2}, …, e_{m} rendszerből kapjuk a következő egyszerű állítást. Lemma 6.18. p ≥ 1 esetén

disc_{ℓ_{p}}(m) ≥ ^{p} √m.

Most nem megyünk bele ℓ_{p} normáktól különböző esetekbe de úgy gondoljuk, hogy a következő sejtés adja meg az univerzális alsó becslést. Sejtés 6.19. Tetszőleges s normára

disc_{s}(m) ≥ √m.

7 Különböző normák

Az s-diszkrepancia természetes általánosítása, ha a vektoraink valamilyen s_{1} normában kicsik, s célunk egy olyan kettévágás, hogy a részek különbsége egy másik s_{2} normában kicsi. Az előző fogalmak formális általánosításaként adódik tehát A = (a_{1}, a_{2}, …, a_{n}) ∈ B_{n,s_{1},m}, és ε ∈ {−1, 1}^{n}-re

disc_{s_{1},s_{2}}(A, ε) = ∥∑_{i=1}^{n} ε_{i}a_{i}∥_{s_{2}} ,

illetve

disc_{s_{1},s_{2}}(A) = min_{ε∈{−1,1}^{n}} disc_{s_{1},s_{2}}(A, ε),

disc_{s_{1},s_{2}}(n, m) = sup_{A∈B_{n,s_{1},m}} disc_{s_{1},s_{2}}(A),

disc_{s_{1},s_{2}}(m) = sup_{n} disc_{s_{1},s_{2}}(n, m).

A lindisc megfelelő függvényei hasonlóan definiálhatók. A diszkrepancia vizsgálatánál néhány speciális ℓ_{p} normára vizsgáltuk az azonos norma esetét. Itt is az ℓ_{1}, ℓ_{2} és ℓ_{∞} norma vizsgálatára fogunk szorítkozni. A legtöbb eset triviális vagy az eddigi vizsgálataink következménye, a rövidség kedvéért az disc_{s_{1},s_{2}}(m)-re kapott eredményeket egy táblázatban foglaljuk össze. Fent azt jelöljük, hogy a vektorok milyen normában kicsik, baloldalon pedig az előjelezés normáját.

ℓ_{1}  ℓ_{2}  ℓ_{∞}
ℓ_{1}  m  m  m ≤ ≤ m√m
ℓ_{2}  √m  √m  (1 − o(1))m ≤ ≤ Km
ℓ_{∞}  ≤ 2  sejtés: ≤ c (1 − o(1))√m ≤ ≤ K√m
Beck-Fiala Komlós-sejtés  Joel Spencer

A diagonálisban levő elemek már ismertek. A többit ezekből a normák közti egyenlőtlenségek alapján lehet kiszámolni. Az egyetlen nemtriviális eset az s_{1} = ℓ_{1}, s_{2} = ℓ_{∞}, illetve az s_{1} = ℓ_{2}, s_{2} = ℓ_{∞}, ez utóbbira a táblázatban szereplő, eddig nem bizonyított eredmény Komlós-sejtés néven vált ismertté. A Beck-Fialával jelzett eredményt bebizonyítjuk most az eredeti lineáris algebrai bizonyítást követve [BeFi]. A Komlós-sejtés kivételével a táblázatban szereplő eredmények mind igazak lineáris diszkrepanciára is, bár ahol a Spencer-által bizonyított K konstans szerepel, ahelyett 2K-t kell írni.

A Beck-Fiala-tétel legegyszerűbb alakja hipergráfok diszkrepanciájáról szól.

Tétel 7.1. Legyen H = {E_{1}, E_{2}, …, E_{m}} egy hipergráf n ponton. Ekkor létezik ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} 2-szinezés, melyre

max_{j∈[m]} | ∑_{i∈E_{j}} ε_{i}| < 2Δ(H),

ahol Δ(H) a H hipergráfban a maximális fokot jelöli.

A hipergráfos kerekítési változat pedig a következőképpen szól, amiből az előző tétel p_{i} = 0 speciális választással adódik.

Tétel 7.2. Legyen H = {E_{1}, E_{2}, …, E_{m}} egy hipergráf n ponton, és p_{i} ∈ [−1, +1], i ∈ [n] számok. Ekkor létezik ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} előjelezés, melyre

max_{j∈[m]} | ∑_{i∈E_{j}}(p_{i} − ε_{i})| < 2Δ(H),

ahol Δ(H) a H hipergráfban a maximális fokot jelöli.

A vektoros alak pedig a következő, ami további formális általánosítás, hiszen ha a (z_{1}, z_{2}, …, z_{n}) mátrix, melynek oszlopai a z_{i} vektorok, megegyezik H incidenciamátrixával, akkor pont az előző alakot kapjuk.

Tétel 7.3. Legyenek z_{1}, z_{2}, …, z_{n} ∈ ℝ^{m} vektorok, ∥z_{i}∥_{ℓ_{1}} ≤ Δ, és p_{i} ∈ [−1, +1], i ∈ [n] számok. Ekkor létezik ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} előjelezés, melyre

max_{j∈[m]} |∑_{i=1}^{n}(p_{i} − ε_{i})z_{i,j}| < 2Δ.

Még másként a diszkrepanciás megfogalmazás.

Tétel 7.4.

lindisc_{ℓ_{1},ℓ_{∞}}(n, m) < 2.

Proof. (7.3 tétel) Tekintünk ε_{i} ∈ [−1, +1] változókat, kezdetben legyen ε_{i} = p_{i}, és ezeket a változókat össze-vissza változtatva beállítani végül −1 vagy +1-re. Kezdetben a „diszkrepancia” tehát 0. Leírjuk az eljárás egy lépését, melyet iterálva jutunk el a jó előjelezéshez. Ha ε_{i} ∈ {−1, +1}, akkor i-t fixnek nevezzük, különben lebegőnek. Ezen indexek halmaza legyen F illetve L. A j sor legyen jó, ha

|∑_{i∈L} z_{i,j}| ≤ Δ,  (13)

különben aktívnak, ezek a halmazok pedig legyenek J illetve A. Minthogy minden oszlop abszolútértékösszege legfeljebb Δ,

|A|Δ < ∑_{j∈A} ∑_{i∈L} |z_{i,j}| ≤ Δ|L|,

tehát több lebegő változó van, mint aktív sor, így létezik ∑_{i∈L} y_{i}(z_{i}|A) = 0 nemtriviális

lineáris összefüggése a lebegő vektorok aktív koodinátáiból álló részvektorainak. Létezik olyan kis λ szám, hogy a lebegő együtthatókon a ε_{i} := ε_{i} + λy_{i} transzformációt végrehajtva legalább egy lebegő együtthatót fixálunk. Amikor egy együttható fix lett, utána az is marad, végül mind fix lesz. Egy sor „diszkrepanciája” 0 marad mindaddig, míg aktív, majd jóvá válik. Ezen sor diszkrepanciája pedig ezután a lebegő együtthatók változásakor változik, és minden együttható kisebb mint 2-vel, változik, az egész sor diszkrepanciája tehát (13) miatt kisebb mint 2Δ.

A Beck-Fiala tétellel kapcsolatban meg kell említenünk a Beck-Fiala-sejtést.

Sejtés 7.5. Legyen H = {E_{1}, E_{2}, …, E_{m}} egy hipergráf n ponton. Ekkor létezik ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} előjelezés, melyre

max_{j∈[m]} | ∑_{i∈E_{j}} ε_{i}| < c√Δ(H),

ahol c abszolút konstans.

A táblázatra visszatérve egy elemről még nem beszéltünk, ami a Komlós-sejtés nevet viseli.

Sejtés 7.6. Legyenek z_{1}, z_{2}, …, z_{n} ∈ B_{ℓ_{2},m} vektorok. Ekkor létezik ε_{1}, ε_{2}, …, ε_{n} ∈ {−1, +1} előjelezés, melyre

∥∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{∞}} ≤ c,

ahol c abszolút konstans.

Érdemes észrevenni, hogy a Komlós-sejtésből következik a Beck-Fiala-sejtés hipergráfokra, hisz ha z_{i} H incidenciamátrixának i. oszlopa, akkor ∥z_{i}∥_{ℓ_{2}} ≤ √Δ(H), s így

∥∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{∞}} ≤ c√Δ(H)

a Komlós-sejtés konstansával. Ezek azonban csak sejtések, a dolgozatnak pedig nem célja belemenni abba, hogy milyen eredmények igazak, melyek közelebb állnak hozzájuk.

8 A Dvoretzky-függvény illetve a diszkrepancia egy általánosítása

8.1 Általános becslések és az ℓ_{1} eset

A Dvoretzky-függvény vizsgálatakor megvizsgáltuk, hogy egy paralelepipedon középpontja, illetve tetszőleges pontja néhány speciális normában milyen messze lehet a hozzá legközelebbi csúcstól. Most ennek a kérdéskörnek egy nagymérvű általánosítását fogjuk vizsgálni. Bárány Imre és V. S. Grinberg munkájából [BaGr].

Tekintsünk most egy s félnormát. A lineáris diszkrepancia esetében adottak a

C_{i} = {z_{i}, −z_{i}} ⊂ B_{s,m}, i ∈ [n] halmazok, α_{i} ∈ [−1, +1], w = ∑_{i=1}^{n} α_{i}z_{i}, s úgy aka-

runk kiválasztani egy c_{i} ∈ C_{i} vektort minden i ∈ [n]-re, hogy a ∥w − ∑_{i=1}^{n} c_{i}∥_{s} távolság

„kicsi” legyen.

Természetes általánosítás, hogy vegyünk tetszőleges C_{i} ⊂ B_{s,m}, i ∈ [n] halmazokat

ahol egy w ∈ ℝ^{m} vektorra w ∈ ∑_{i=1}^{n} conv(C_{i}), és ki akarunk választani minden i ∈ [n]-re

egy c_{i} ∈ C_{i} elemet, melyre ∥w − ∑_{i=1}^{n} c_{i}∥_{s} kicsi.

Legyen

κ_{s}(n, m) = sup_{C_{i}∈B_{s,m}i∈[n]} min_{c_{i}∈C_{i},i∈[n]} ∥∑_{i=1}^{n} c_{i}∥_{s} ,

és

κ_{s}(m) = sup_{n} κ_{s}(n, m).

Nyilván

lindisc_{s}(n, m) ≤ κ_{s}(n, m),

s így a lindisc_{s}(n, m)-re eddig adott alsó becslések érvényben maradnak κ_{s}(n, m)-re is.

A következő lemma a 6.1 lemma, és a Caratheodory-tétel egy közös általánosítása, ami nem véletlen, hiszen minden esetben a bázis megoldás létezésének egy speciális esetéről van szó.

Lemma 8.1. ([BaGr]) Legyen C_{i} ⊂ ℝ^{m}, i ∈ [n], w ∈ ∑_{i=1}^{n} conv(C_{i}). Ekkor léteznek

olyan α_{i} : C_{i} → ℝ véges tartójú függvények, hogy

∑_{i=1}^{n} ∑_{z∈C_{i}} α_{i}(z)z = w,  (14)
∑_{z∈C_{i}} α_{i}(z) = 1  i ∈ [n],  (15)
α_{i}(z) ≥ 0  i ∈ [n], z ∈ C_{i},  (16)

hogy

|{z ∈ C_{i} : α_{i}(z) > 0, i ∈ [n]}| ≤ m + n.

Az n = 1 esetben a Caratheodory-tételt kapjuk, a C_{i} = {z_{i}, −z_{i}} esetben pedig a 6.1 lemmát.

Proof. A (14)-(15)-(16) rendszer megoldáshalmaza korlátos, és a feltétel szerint nem üres. Nyilván feltehető, hogy minden C_{i} véges. Ekkor a rendszer egy bázis megoldásában

legalább ∑_{i=1}^{n} |C_{i}|−m−n változó egyenlőséggel teljesíti a hozzá (16)-ben tartozó feltételt,

tehát teljesül a kívánt becslés.

Nézzük meg, hogy mit állíthatunk tetszőleges normában.

Tétel 8.2. ([BaGr]) Legyen s szimmetrikus félnorma, C_{i} ⊂ B_{s,m}, i ∈ [n], ahol w ∈

∑_{i=1}^{n} conv(C_{i}). Ekkor léteznek c_{i} ∈ C_{i}, i ∈ [n], hogy

∥∑_{i=1}^{n} c_{i} − w∥_{s} ≤ min(n, m),

azaz

κ_{s}(n, m) ≤ min(n, m).

Proof. Az n ≤ m eset azonnal adódik, így legyen n > m. Tekintsük a 8.1 lemma lemma szerinti α_{i}(z) együtthatókat. Legyen a_{i} = |{z ∈ C_{i} : α_{i}(z) > 0}|. (15) miatt a_{i} ≥ 1, minden i-re van pozitív együttható, de a lemma állítása szerint legfeljebb csak m olyan van, ahol több együttható is pozitív. Ezen maradék i-kre kell tehát választanunk, válasszuk egy olyan c_{i} ∈ C_{i} elemet, melyre α_{i}(c_{i}) = max{α_{i}(z) : z ∈ C_{i}}. Ekkor

∑_{i=1}^{n} c_{i} − w = ∑_{i=1}^{n} (c_{i} − ∑_{z∈C_{i}} α_{i}(z)z) = ∑_{i=1}^{n} ((1 − α_{i}(c_{i}))c_{i} − ∑_{z∈C_{i},z≠c_{i}} α_{i}(z)z) ,

tehát

∥∑_{i=1}^{n} c_{i} − w∥_{s} ≤ ∑_{i=1}^{n} ((1 − α_{i}(c_{i})) + ∑_{z∈C_{i},z≠c_{i}} α_{i}(z)) = 2 ∑_{i=1}^{n} (1 − α_{i}(c_{i})) ≤

≤ ∑_{i=1}^{n}(a_{i} − 1) ≤ m.

Egyedül az utolsóelőtti egyenlőtlenség nem látszik azonnal, ami viszont ekvivlens 3−a_{i} ≤ 2α_{i}(c_{i})-vel, a_{i} = 1-re α_{i}(c_{i}) = 1, a_{i} ≥ 3-ra triviális, a_{i} = 2-re pedig c_{i} választása miatt adódik. Érdekes, hogy a lemma alkalmazása után a tétel erdeménye szempontjából csak azokra az i-kre fontos hogy mit választunk, ahol két vektor közül kell választani.

Megjegyzés 8.3. A becslés élessége azonnal adódik a m ≤ disc_{ℓ_{1}}(m) egyenlőtlenségből.

8.2 Az ℓ_{2} norma

Természetesen megvizsgálhatjuk a Dvoretzky-függvény vizsgálatához hasonlóan, hogy milyen eredményeket kaphatunk más speciális normákban. ℓ_{2} normában is ugyanazzal a gondolatmenettel ugyanazt a becslést adhatjuk. Talán azért is érdemes végiggondolni, mert a [BaGr] cikk csak megemlíti ezt az eredményt, mint Grinberg egy publikálatlan erdeményét, de nem megy bele a részletekbe.

Tétel 8.4. Legyenek C_{i} ⊂ B_{ℓ_{2},m}, i ∈ [n], ahol w ∈ ∑_{i=1}^{n} conv(C_{i}). Ekkor léteznek c_{i} ∈ C_{i},

i ∈ [n], hogy

∥∑_{i=1}^{n} c_{i} − w∥_{ℓ_{2}} ≤ √min(n, m),

azaz

κ_{ℓ_{2}}(n, m) ≤ √min(n, m).

Proof. Tekintsük a 8.1 lemma szerinti α_{i}(z) együtthatókat. Vegyünk egy véletlen választást, legyenek a C_{i}-ből választott elemek ζ_{i}, (i ∈ [n]) független valószínűségi változók, mégpedig

ℙ (ζ_{i} = z) = α_{i}(z), i ∈ [n], z ∈ C_{i}

eloszlással. Legyen az előzőekhez hasonlóan a_{i} = |{z ∈ C_{i} : α_{i}(z) > 0}|. Ekkor

𝔼 ∥w − ∑_{i=1}^{n} ζ_{i}∥_{ℓ_{2}}^{2} = 𝔼 ∥∑_{i=1}^{n} ∑_{z∈C_{i}} α_{i}(z)z − ∑_{i=1}^{n} ζ_{i}∥_{ℓ_{2}}^{2} = 𝔼 ∥∑_{i=1}^{n} ( ∑_{z∈C_{i}} α_{i}(z)z − ζ_{i})∥_{ℓ_{2}}^{2} =

= ∑_{i∈[n],j∈[n]} 𝔼 [( ∑_{z∈C_{i}} α_{i}(z)z − ζ_{i})^{T} ( ∑_{z∈C_{j}} α_{j}(z)z − ζ_{j})] =

= ∑_{i∈[n]} 𝔼 ∥ ∑_{z∈C_{i}} α_{i}(z)z − ζ_{i}∥_{ℓ_{2}}^{2} = ∑_{i∈[n]} ∑_{x∈C_{i}} α_{i}(x) ∥ ∑_{z∈C_{i}} α_{i}(z)z − x∥_{ℓ_{2}}^{2} =

= ∑_{i∈[n]} ∑_{x∈C_{i}} α_{i}(x) [∥ ∑_{z∈C_{i}} α_{i}(z)z∥_{ℓ_{2}}^{2} + ∥x∥_{ℓ_{2}}^{2} − 2 ∑_{z∈C_{i}} α_{i}(z)z^{T} x] =

= ∑_{i∈[n]} [∥ ∑_{z∈C_{i}} α_{i}(z)z∥_{ℓ_{2}}^{2} + ∑_{x∈C_{i}} α_{i}(x) ∥x∥_{ℓ_{2}}^{2} − 2 ( ∑_{z∈C_{i}} α_{i}(z)z^{T} ) ( ∑_{x∈C_{i}} α_{i}(x)x)] =

= ∑_{i∈[n]} [ ∑_{x∈C_{i}} α_{i}(x) ∥x∥_{ℓ_{2}}^{2} − ∥ ∑_{z∈C_{i}} α_{i}(z)z∥_{ℓ_{2}}^{2} ] =

= ∑_{i∈[n],a_{i}>1} [ ∑_{x∈C_{i}} α_{i}(x) ∥x∥_{ℓ_{2}}^{2} − ∥ ∑_{z∈C_{i}} α_{i}(z)z∥_{ℓ_{2}}^{2} ] ≤

≤ ∑_{i∈[n],a_{i}>1} ∑_{x∈C_{i}} α_{i}(x) ∥x∥_{ℓ_{2}}^{2} ≤ min(n, m),

a lemma miatt, hiszen legfeljebb min(n, m) olyan i van, ahol még választani kell.

8.3 Az ℓ_{∞} eset

Az s = ℓ_{∞} esetben is teljesen hasonló becslést adhatunk, mint a diszkrepanciás vizsgálatunknál.

Tétel 8.5. Legyenek C_{i} ⊂ B_{ℓ_{∞},m}, i ∈ [n], ahol w ∈ ∑_{i=1}^{n} conv(C_{i}). Ekkor léteznek

c_{i} ∈ C_{i}, i ∈ [n], hogy

∥∑_{i=1}^{n} c_{i} − w∥_{ℓ_{∞}} ≤ √2 min(n, m) ln(2m),

Ezt nem bizonyítjuk most be, az eddig látottak alapján az olvasó ki tudja találni, hogy hogyan is nézne ki a bizonyítás. Az alkalmazásokra való tekintettel inkább elkezdünk foglalkozni egy speciális esettel, hisz a 6.11 tétel erre még további lehetőséget ad.

8.4 Egy alkalmazás: MIP és torlódásminimalizálás osztatlan folyamban

Egy a [BaGr] cikk feladataihoz, illetve a most tárgyalt kiválasztási feladatokhoz hasonlót fogjuk tárgyalni, amely valójában az ℓ_{∞} esethez áll a legközelebb.

MIP (minimax integer program) [Ra, RT, Sr2, Sr1, LRS, Lu]. A MIP egy vegyes programozási feladat, melynek változói W, illetve {x_{i}, j : i ∈ [n], j ∈ [l_{i}]}, az l_{i}, i ∈ [n]

pozitív egészek pedig adottak. N = ∑_{i=1}^{n} l_{i}. Jelölje x az x_{i}, j változókból alkotott N-

dimenziós vektort. A cél W minimalizálása a következő feltételek mellett:

• ∑_{j∈[l_{i}]} x_{i,j} = 1,

• Ax ≤ W̄, ahol A ∈ [0, 1]^{m×M}, és W̄ az az m-dimenziós oszlopvektor, melynek minden eleme W,

• x_{i,j} ∈ {0, 1}.

Gondoljunk bele egy kicsit, hogy miről is van szó. Adott egy A mátrix, melynek az oszlophalmaza n részre van particionálva, s minden részből ki kell választani pontosan egy vektort, úgy, hogy ezen vektorok összege a lehető legkisebb legyen. A MIP természetesen általában NP-nehéz. A MIP probléma számos helyen felmerül, mi egy egyszerű közelítő megoldását, és egy alkalmazását fogjuk érinteni.

Hogy merülhet fel egy ilyen MIP. Látszik a címből, hogy például az osztatlan folyam problémánál. Tegyük fel, hogy adott egy G = (V, E) irányítatlan gráf, |E| = m, {s_{i}, t_{i}}, i ∈ [n] pontpárok, s minden i-re egy egységnyi igény az s_{i} és t_{i} közt, s az ezen inputokkal definiált többtermékes folyamproblémát (multicommodity flow, MCF) kell úgy megoldani, hogy az elvezetett folyam a lehető legkisebb uniform kapacitásba beleférjen. Az osztatlan folyamot úgy kapjuk, ha még azt is megköveteljük, hogy minden {s_{i}, t_{i}} párra az ő igényüket kielégítő folyam úton legyen elvezetve, ne pedig egy általános folyamon. Ez az osztatlan folyam probléma (unsplittable flow, UFP) egyenlő egységnyi igényekkel.

Az UFP mint egészértékű programozási feladat természetes LP-relaxációjaként adódik az MCF. Tegyük fel, hogy az így adódó LP-feladatra ismert egy optimális megoldásunk, azaz egy optimális többtermékes osztott folyam. Bontsunk szét minden i-re az egységnyi értékű s_{i}-t_{i} folyamot s_{i}-t_{i} utak konvex kombinációjára. Legyen i-re ezen utak száma l_{i}. Feltehető l_{i} ≤ m. Ha úgy akarjuk az UFP egy közelítő megoldását kapni, hogy az így kapott l_{i} út közül kiválasztunk egyet, akkor pont egy MIP-et kapunk, (speciálisan úgy, hogy az A mátrix oszlophalmaza i. partíciórészébe l_{i} darab út incidenciavektora van beírva.) Hagyjuk most az osztatlan folyamos alkalmazást, s foglalkozzunk az általános MIP feladattal.

Oldjuk meg tehát először a MIP LP-relaxációját. Ez annyit jelent, hogy az összes korábbi feltétel megmarad, egyedül az x_{i,j} ∈ {0, 1} feltételeket relaxáljuk a x_{i,j} ∈ [0, 1] feltételekkel. Legyen x_{i,j}^{⋆}, W^{⋆} egy optimális bázis megoldása az LP-relaxációnak. Az így kapott megoldással fogunk definiálni egy valószínűségeloszlást az A oszlopain, s eszerint alkalmazunk véletlen kerekítéses eljárást. Minthogy bázis megoldásunk van, a 8.1 lemmából adódik, hogy legfeljebb m olyan x_{i,j}^{⋆} van, amely nem 0, és nem 1, tehát feltehető, hogy l_{i} ≤ m, minden i ∈ [n]-re. Legyen z ∈ {0, 1}^{N} a véletlenül kerekített vektor, mégpedig úgy, hogy minden i ∈ [n]-re függetlenül, pontosan egy z_{i,j}-t állítunk 1-re, a többi j ∈ [l_{i}]-re z_{i,j} legyen 0, mindezt pedig

ℙ (z_{i,j} = 1) = x_{i,j}^{⋆}

eloszlással. Valójában tehát n darab független valószínűségi változónk van, mégpedig hogy melyik oszlopot választjuk az egyes i ∈ [n]-ekre. Sajnos egy elég bonyolult indexelést kell használnunk, az A mátrix k. sora, és (r, s) oszlopa által kiválasztott elem legyen A_{k,(r,s)}, ahol k ∈ [m], r ∈ [n], és s ∈ [l_{r}]. Legyen

X_{k,r} = ∑_{s∈[l_{r}]} A_{k,(r,s)}x_{r,s}^{⋆}, Z_{k,r} = ∑_{s∈[l_{r}]} A_{k,(r,s)}z_{r,s}^{⋆}.

Ekkor 𝔼Z_{k,r} = X_{k,r}, k ∈ [m], r ∈ [n],

𝔼 ∑_{r∈[n]} Z_{k,r} = ∑_{r∈[n]} X_{k,r} ≤ W, k ∈ [m].

Az A mátrix (r, s)-sel indexelt oszlopát A_{(r,s)}-sel jelölve {A_{(r,s)} : s ∈ [l_{r}]} ⊂ B_{ℓ_{∞},m}, és

Ax ∈ ∑_{r∈[n]} conv ({A_{(r,s)} : s ∈ [l_{r}]}) .

Úgy akarunk kerekíteni, hogy az Az kerekítés egyik koordinátája se legyen sokkal nagyobb W^{⋆}-nál. Az összes feltétel teljesül, így a 8.5 tétel első próbálkozásként alkalmazható, így létezik olyan kerekítés, hogy

∥Az − Ax∥_{ℓ_{∞}} ≤ √2 min(n, m) ln(2m).

A minimumképzés itt azért szerepelhet, mivel feltettük, hogy bázis megoldásról van szó. Mivel nem közvetlenül az ℓ_{∞} normáról van szó csak azt akarjuk, hogy felfelé ne térjen el nagyon a kerekített Az vektor, ezért kis javítással

(Az)_{i} ≤ W^{⋆} + √2 min(n, m) ln m.

Tétel 8.6. Létezik olyan megoldása a torlódásminimalizálási feladatnak, melyben

W ≤ W^{⋆} + √2 min(n, m) ln m,

ahol W^{⋆} az LP-relaxáció optimális megoldása.

Ezzel az eredménnyel már régen nem lehetne cikket írni. De tudjuk, hogy az 8.5 tétel bizonyításában a 6.11 tételt használtuk, mint a valószínűségi változó várható értékétől való nagy eltérésének valószínűségét becslő egyenlőtlenséget. Azt a specialitását fogjuk kihasználni a feladatnak, hogy az itt vizsgált valószínűségi változók az egységgömbnek csak egy kis részén, mégpedig a pozitív koordinátákkal rendelkező részén veszik fel pozítív valószínűséggel értékeiket, sőt az egyes változók csak 0-t és 1-et tudnak felvenni. Emiatt egy másik nagy-eltérés egyenlőtlenséget fogunk alkalmazni [Ra].

Tétel 8.7. ([Ra]) Legyenek X_{1}, X_{2}, …, X_{n} független indikátor valószínűségi változók,

a_{i} ∈ (0, 1], 𝔼 (X_{i}) = p_{i}. Legyen továbba X = ∑_{i=1}^{n} a_{i}X_{i}, 𝔼X = μ. Ekkor δ > 0 esetén

ℙ (X > (1 + δ)μ) < ( e^{δ} ; (1 + δ)^{(1+δ)} )^{μ} .

Az így kapott korlátra vezessük be a következő jelölést:

B(μ, δ) = ( e^{δ} ; (1 + δ)^{(1+δ)} )^{μ} .

Ez a függvény δ > 0-ra monoton csökken, így legyen

D(μ, p) = inf{δ > 0 : B(μ, δ) ≤ p},

azaz B(μ, D(μ, p)) = p. Néhány számolással igazolható összefüggés még kell ezekről a függvényekről.

Lemma 8.8. μ > ln 1 ; p esetén

D(μ, p) ≤ (e − 1)√\begin{matrix}ln & 1 ; p \\ μ \end{matrix} ,

μ ≤ ln 1 ; p esetén pedig

D(μ, p) ≤ e ln 1 ; p ; μ ln [ e ln 1 ; p ; μ ].

Igazolható továbbá, hogy 0 < μ_{1} ≤ μ_{2}, δ > 0 esetén

B (μ_{1}, μ_{2} ; μ_{1} δ) ≤ B(μ_{2}, δ).

Mostmár kimondható a tétel.

Tétel 8.9. Létezik olyan megoldása a MIP-nek, melyre

W ≤ W^{⋆} (1 + D(W^{⋆}, 1 ; m)) ,  (17)

sőt

W ≤ W^{⋆} (1 + D(W^{⋆}, 1 ; 2m))  (18)

értékű hatékony randomizált algoritmussal ki is számolható.

Proof.

ℙ ((Az)_{k} > (Ax^{⋆})_{k} + W^{⋆}D (W^{⋆}, 1 ; m)) < B ((Ax^{⋆})_{k}, W^{⋆}D (W^{⋆}, 1 ; m) ; (Ax^{⋆})_{k}) ≤

B (W^{⋆}, D (W^{⋆}, 1 ; m)) = 1 ; m,

tehát a soronkénti hibavalószínűségek összege kisebb mint 1. Az állítás második felét onnan kapjuk, hogy ott a hibavalószínűségek összege kisebb mint 1 2, így a véletlen kerekítést t-szer alkalmazva a hiba valószínűsége kisebb mint 2^{−t}.

Következmény 8.10. Létezik olyan megoldás, melyre W^{⋆} > ln m esetén

W ≤ W^{⋆} + (e − 1)√W^{⋆} ln m,

W^{⋆} ≤ ln m esetén pedig

W ≤ W^{⋆} + \begin{matrix}e ln m \\ ln & [ e ln m ; W^{⋆}] \end{matrix}.

Az első esetben tehát korábbi eredményünk javítását kapjuk, azzal a feltétellel persze, hogy W^{⋆}, az LP-optimum „viszonylag nagy”.

Raghavan randomizált algoritmusa a (17) korláttal elvezet egy hatékony determinisztikus algoritmushoz, cikkének tulajdonképpen ez a fő eredménye. A feltételes válószínűségek módszere nem alkalmazható, ugyanis az adódó feltételes valószínűségeket nem lehet hatékonyan kiszámolni. A nagy-eltérés egyenlőtlenség bizonyítása azonban elvezet olyan pesszimista becslő függvényekhez (pessimistic estimators), melyekre már végre lehet hajtani egy hasonló eljárást. Ez a módszer úgy adódik, hogy a feltételes valószínűségeket bizonyos feltételes várható értékekkel becsüljük fölül, melyek már hatékonyan számolhatóak, és ezekre hajtunk végre egy feltételes valószínűségek módszerét. Később egy dinamikus előjelezési feladatra ezt részletesen tárgyaljuk. (Egy pillanatra érdemes meggondolni, hogy a feltételes várható értékek, és a feltételes valószínűségek módszere az valahogy ugyanaz, hiszen a valószínűség egy indikátor várható értéke.)

Ezt az eredményt további ritkaság esetén a Lovász Local Lemma [EL] segítségével lehetne javítani. Ha a MIP A mátrixában minden oszlopban legfeljebb D és minden sorban legfeljebb T nemnulla elem van, akkor a fenti tételben m mindenhol eDT -re cserélhető. A hatékony randomizált algoritmus, s a derandomizáció Beck József nevéhez fűződik [Be].

9 Dinamikus diszkrepanciák

9.1 Általános becslések, és ℓ_{1} norma

Az eddigi vizsgálataink nagyrésze olyan diszkrepanciaproblémákra esett, ahol vektorokat akartunk előjelezni úgy, hogy az összeg 0-hoz közel legyen, vagy ahol bizonyos vektorhalmazokból ki akartunk választani egy-egy elemet, úgy, hogy az összeg közel legyen egy bizonyos vektorhoz. Az algoritmikus meggondolásainkkor pedig gyakran úgy jártunk el, –mondjuk az előjelezési feladat esetén–, hogy vettük a vektorokat egy sorrendben, s mindhez meghatároztuk az előjelt, a lerögzített előjeleket pedig már nem változtattuk.

Miért ne tehetnénk fel azt az általánosabb kérdést, hogy legyenek az ilyen sorrendben kapott előjelezett részletösszegek is kicsik. Az előjelezési feladatra már bevezettünk egy DVB nevű feladatot, ennek vizsgálata helyett azonban most újra egy általánosítást veszünk, szintén Bárány és Grinberg cikkéből [BaGr].

Legyen s újra egy (szimmetrikus) félnorma ℝ^{m}-en. C_{i} ⊂ B_{s,m}, 0 ∈ conv(C_{i}), i ∈ [n]. Olyan c_{i} ∈ C_{i}, i ∈ [n] kiválasztást keresünk, hogy

max_{1≤t≤n} ∥∑_{i=1}^{t} c_{i}∥_{s}

kicsi legyen. A következő tétel csak lineáris algebrai eszközöket használva állítja, hogy a normától és a vektorok számátől független felső becslés is adható. Olyannyira, hogy a tétel nem csak véges n-ekre működik.

Tétel 9.1. ([BaGr]) Legyen s (szimmetrikus) félnorma ℝ^{m}-en. C_{i} ⊂ B_{s,m}, 0 ∈ conv(C_{i}), i ∈ ℕ. Ekkor létezik c_{i} ∈ C_{i}, i ∈ ℕ kiválasztás, hogy

max_{t∈ℕ} ∥∑_{i=1}^{t} c_{i}∥_{s} ≤ 2m.

Proof. Először meghatározunk egy majdnem-kiválasztást, ahol dimenziónyi halmaz kivételével választunk, majd ezt kiegészítjük az olyan helyeken ahol még nem választottunk, tetszőlegesen.

Meghatározunk indukcióval egy A_{0} ⊂ A_{1} ⊂ A_{2} ⊂ … halmazsorozatot, ahol |A_{j}| = j,

A_{j} ⊂ [m + j], és választunk minden i ∈ ⋃_{j=1}^{∞} A_{j} indexre egy c_{i} ∈ C_{i} elemet, hogy

B_{j} = [m + j] \ A_{j} jelöléssel

0 ∈ ∑_{i∈A_{j}} c_{i} + ∑_{i∈B_{j}} conv(C_{i}).  (19)

j = 0 esetén A_{j} = ∅, B_{j} = [m].

Ha már j-re rendelkezünk megfelelő kiválasztással, akkor

− ∑_{i∈A_{j}} c_{i} ∈ ∑_{i∈B_{j}} conv(C_{i}) ⊂ ∑_{i∈B_{j}∪{m+j+1}} conv(C_{i}).

A 8.1 lemma alkalmazálával adódik, hogy ekkor kiválasztható egy i_{0} ∈ B_{j} ∪ {m + j + 1} index, és c_{i_{0}} ∈ C_{i_{0}}, hogy

− ∑_{i∈A_{j}} c_{i} ∈ c_{i_{0}} + ∑_{i∈B_{j}∪{m+j+1}\i_{0}} conv(C_{i}).

Legyen tehát A_{j+1} = A_{j} ∪ i_{0}, és c_{i_{0}} az új kiválasztott elem, a c_{i_{0}} helyre. m kivétellel minden indexre választottunk, a többi i indexre vegyünk tetszőleges c_{i} ∈ C_{i} elemet. Tehát tetszőleges t = j + m természetes számra (19) miatt, és |B_{j}| = m-et használva

∑_{i=1}^{t} c_{i} = ∑_{i∈A_{j}} c_{i} + ∑_{i∈B_{j}} c_{i} ∈ − ∑_{i∈B_{j}} conv(C_{i}) + ∑_{i∈B_{j}} c_{i} ⊂ 2mB_{s,m}.

t < m-re pedig triviálisan adódik az állítás.

Korábbi mesterkedéseinkből adódik, hogy s = ℓ_{1} választással a konstans szorzótól eltekintve éles az eredmény.

Nyilván felmerül a kérdés –a korábbiakhoz hasonlóan–, hogy más speciális normákban, és véges sorozaton milyen jobb becslések adhatók. Sem az előző tételhez hasonlót nem sikerült találni, sem olyan eredményeket, melyek véges sorozat esetén a C_{i} halmazok számától független becslést adna. Úgy tűnik, ezek között számos nyitott kérdés van, már a DVB feladat esetén is. Lehet sejteni, hogy ℓ_{2} illetve ℓ_{∞} normában a korábbi eredményekhez hasonló igaz.

Nyitott kérdés 9.2. Legyenek z_{1}, z_{2}, …, z_{n} ∈ B_{ℓ_{2},m} vektorok. Létezik-e olyan ε ∈ {−1, +1}^{n} előjelezés, hogy

max_{1≤t≤n} ∥∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{2}} = O(√m).

Ez ugyanígy felmerül ℓ_{∞} normában is.

Nyitott kérdés 9.3. Legyenek z_{1}, z_{2}, …, z_{n} ∈ B_{ℓ_{∞},m} vektorok. Létezik-e olyan ε ∈ {−1, +1}^{n} előjelezés, hogy

max_{1≤t≤n} ∥∑_{i=1}^{n} ε_{i}z_{i}∥_{ℓ_{∞}} = O(√m).

Spencer [Sp2] igenlő választ adott az előző nyitott kérdés azon esetére, melyben a dimenzió, és a vektorok száma azonos.

Tétel 9.4. Legyenek z_{1}, z_{2}, …, z_{m} ∈ B_{ℓ_{∞},m} vektorok. Ekkor létezik olyan ε ∈ {−1, +1}^{m} előjelezés, hogy

max_{1≤t≤m} ∥∑_{i=1}^{m} ε_{i}z_{i}∥_{ℓ_{∞}} = O(√m).

A bizonyítás az [Sp4]-ben használthoz hasonló eszközöket használ, melyekről már a 6.13 tétel kapcsán már szóltunk. Máig nem ismert algoritmus, mely a kívánt korláttal rendelkező előjelezést előállítaná. A nyitott kérdések megfogalmazása után olyan becslésekre fogunk ezentúl töredekni, melyek függenek a C_{i} halmazok számától. Kis n-ekre ezek nyilván adhatnak jobb becslést a korábbi eredményeknél. A másik megközelítés egy on-line irány, az ide tartozó tételeket pedig legszemléletesebben matematikai játékok keretén belül lehet megfogalmazni.

10 Kiegyensúlyozó játékok

Az itt szereplő kiegyensúlyozó játékok a szakirodalomban balancing game néven ismertek. Ebben a dolgozatban a kiegyensúlyozó játékok fordítást fogjuk használni. Kezdjük mindjárt azzal, hogy Bárány Imre és V. S. Grinberg 9.1 tételének a következő szemléletes jelentés adható egy játék alakjában.

1. Játék. Adott egy s félnorma ℝ^{m}-en. Két játékos játszik Alíz és Bea. A játék két lépésből áll, mindkét játékos egyet lép. Alíz az első lépésben kiválaszt egy z_{i} ∈ B_{s,m}, i ∈ ℕ végtelen sorozatot. Bea ezután választ egy ε_{i} ∈ {−1, +1}, i ∈ ℕ végtelen előjelsorozatot. Alíznak a játék végen kifizetik a

sup_{t∈ℕ} ∥∑_{i=1}^{t} ε_{i}z_{i}∥_{s}

összeget. A játék értéke

val_{s}^{(1)}(m) = sup_{z∈B_{s,m}^{ℕ}} inf_{ε∈{−1,+1}^{ℕ}} sup_{t∈ℕ} ∥∑_{i=1}^{t} ε_{i}z_{i}∥_{s} .

Alíz célja tehát, hogy az előjelezett vektorok összegzésekor kapott trajektória messzire menjen, míg Bea közel akarja azt tartani az origóhoz. A játék természetes általánosítása a következő.

2. Játék. Az 1. Játéktól ez csak abban különbözik, hogy Alíz az első lépésben egy C_{i} ⊂ B_{s,m}, i ∈ ℕ végtelen sorozatot választ ki, ahol 0 ∈ conv(C_{i}), Bea ezután kiválaszt minden i ∈ ℕ-re egy c_{i} ∈ C_{i} vektort. Alíznak a játék végén kifizetik a

sup_{t∈ℕ} ∥∑_{i=1}^{t} c_{i}∥_{s}

összeget. A játék értéke

val_{s}^{(2)}(m) = sup_{z∈B_{s,m}^{ℕ}} inf_{c_{i}∈C_{i}} sup_{t∈ℕ} ∥∑_{i=1}^{t} c_{i}∥_{s} .

Láttuk, hogy a játék értéke véges, val_{s}^{(2)}(m) ≤ 2m, és m ≤ val_{ℓ_{1}}^{(2)}(m). Más speciális és érdekes normákban nem ismerjük ezen játék értékének nagyságrendjét.

A következő játék már véges lesz, hisz végtelen sok lépés esetén –mint látni fogjuk–, a játék értéke nem lenne véges.

3. Játék. Az 2. Játéktól ez abban különbözik, hogy a játékosok felváltva lépnek, Alíz az i lépésben egy C_{i} ⊂ B_{s,m}, 0 ∈ conv(C_{i}) halmazt választ, Bea ezután kiválaszt egy c_{i} ∈ C_{i} vektort, s utána jön Aliz majd Bea j + 1-edik lépése. A játék n lépésből áll. Alíznak a játék végén kifizetik a

max_{t∈[n]} ∥∑_{i=1}^{t} c_{i}∥_{s}

összeget. A játék értéke

val_{s}^{(3)}(n, m) = sup_{z∈B_{s,m}^{[n]}} inf_{c_{i}∈C_{i}} max_{t∈[n]} ∥∑_{i=1}^{t} c_{i}∥_{s} .

Triviális, hogy val_{s}^{(3)}(n, m) ≤ n.

10.1 A kiegyensúlyozó játék ℓ_{2} normában

Most a 3. Játék s = ℓ_{2} esetének értékét gondoljuk meg. Ez a játékos megfogalmazás valójában a Bárány és Grinberg által vizsgált kiválasztási feladat on-line esete. Hasonló eredmény olvasható Spencer [Sp1] cikkében az előjelezési esetre. Tegyük fel általában, hogy m ≥ 2.

Tétel 10.1. Legyen C_{i} ⊂ B_{ℓ_{2},m}, 0 ∈ conv(C_{i}), i ∈ ℕ. Ekkor létezik c_{i} ∈ C_{i}, i ∈ ℕ kiválasztás, hogy

∥∑_{i=1}^{t} c_{i}∥_{ℓ_{2}} ≤ √t,

és ez on-line ki is számolható, tehát a t lépésben csak a ∑_{i=1}^{t−1} c_{i} állapotot, és az új C_{t}

halmazt kell ismernünk a c_{t} ∈ C_{t} elem kiválasztásához. A játékok nyelvén

val_{ℓ_{2}}^{(3)}(n, m) = √n.

Proof. Tegyük fel, hogy t − 1-ig készen vagyunk, és

∥∑_{i=1}^{t−1} c_{i}∥_{ℓ_{2}} ≤ √t − 1.

A feltételek szerint létezik olyan α_{t} : C_{t} → [0, 1] függvény, melynek a tartója legfeljebb m + 1 elemű, és

∑_{x∈C_{t}} α_{t}(x)x = 0,  (20)
∑_{x∈C_{t}} α_{t}(x) = 1.  (21)

A C_{t} többi elemét elhagyva feltehető, hogy véges. Ekkor olyan x ∈ C_{t}-t kell választani, melyre

∥∑_{i=1}^{t−1} c_{i} + x∥_{ℓ_{2}}^{2} = ∥∑_{i=1}^{t−1} c_{i}∥_{ℓ_{2}}^{2} + ∥x∥_{ℓ_{2}}^{2} + 2 ∑_{i=1}^{t−1} c_{i}^{T} x

legfeljebb t. Viszont ekkor

∑_{x∈C_{t}} α_{t}(x) ∥∑_{i=1}^{t−1} c_{i} + x∥_{ℓ_{2}}^{2} =

= ∑_{x∈C_{t}} α_{t}(x) ∥∑_{i=1}^{t−1} c_{i}∥_{ℓ_{2}}^{2} + ∑_{x∈C_{t}} α_{t}(x) ∥x∥_{ℓ_{2}}^{2} + 2 ∑_{x∈C_{t}} α_{t}(x) ∑_{i=1}^{t−1} c_{i}^{T} x ≤

≤ t − 1 + 1 + 2 (∑_{i=1}^{t−1} c_{i})^{T} ∑_{x∈C_{t}} α_{t}(x)x = t,

tehát valamelyik normanégyzet legfeljebb t, hiszen egy kovex kombinációjuk legfeljebb t volt. Válasszuk a hozzá tartozó x ∈ C_{t} elemet.

Az állítás második feléhez tegyük fel megmondjuk Alíz választását minden lépésben.

t−1 lépés után a játék a ∑_{i=1}^{t−1} c_{i} pozicióban áll, Alíz válasszon egy olyan z_{t} vektort, amire

∑_{i=1}^{t−1} c_{i} és z_{t} merőlegesek, ∥z_{t}∥_{ℓ_{2}} = 1, és legyen C_{t} = {z_{t}, −z_{t}}. Ha Alíz így játszik, akkor

∥∑_{i=1}^{t} c_{i}∥_{ℓ_{2}} = √t.

10.2 ℓ_{∞} norma

Ez az az eset, ami az alkalmazások kapcsán a legfontosabbnak bizonyul, így egy kicsit fonomabb vizsgálatot fogunk végezni. Nem lepi meg az olvasót a következő tétel, melyet egy exponenciális súlyfüggvényen alapuló algoritmussal be lehet látni, [Sp1]-ben megtalálható a bizonyítás az előjelezési esetre.

Tétel 10.2. Legyen C_{i} ⊂ B_{ℓ_{∞},m}, 0 ∈ conv(C_{i}), i ∈ [n]. Ekkor létezik c_{i} ∈ C_{i}, i ∈ [n] kiválasztás, hogy

∥∑_{i=1}^{t} c_{i}∥_{ℓ_{∞}} ≤ √2n ln(2m), t ∈ [n]

és ez on-line ki is számolható, tehát a t lépésben csak a ∑_{i=1}^{t−1} c_{i} állapotot, és az új C_{t}

halmazt kell ismernünk a c_{t} ∈ C_{t} elem kiválasztásához. Játékokra átfogalmazva

(1 − o(1))√n ln n ≤ val_{ℓ_{∞}}^{(3)}(n, m) ≤ √2n ln(2m).

Proof. A bizonyítás valójában egy valószínűségi módszer derandomizációjának is felfogható, mi ezt egy tisztán determinisztikus algoritmus alakjában fogjuk megadni.

Definiálunk egy súlyfüggvényt, s mindig ezt minimalizálva választjuk ki megfelelő c_{i} ∈ C_{i} elemet. Legyen w : ℝ^{m} → ℝ,

w(x) = ∑_{j=1}^{m} cosh(βx_{j}), β = √2 ln(2m)/n.

Legyen s_{t} = ∑_{k=1}^{t} c_{k}. Kezdetben s_{0} = 0. Ha már ismert s_{t−1} és C_{t}, c_{t} ∈ C_{t}-t úgy

választjuk, hogy w(s_{t}) minimális legyen. Az ℓ_{2} esethez hasonlóan választunk egy olyan α_{t} : C_{t} → [0, 1] függvényt, melynek a tartója legfeljebb m + 1 elemű, és

∑_{x∈C_{t}} α_{t}(x)x = 0,  (22)
∑_{x∈C_{t}} α_{t}(x) = 1.  (23)

A C_{t} többi elemét elhagyva feltehető, hogy véges. Ekkor

w(s_{t}) = min{w(s_{t−1} + x) : x ∈ C_{t}} ≤ ∑_{x∈C_{t}} α_{t}(x)w(s_{t−1} + x) =

= ∑_{j=1}^{m} ∑_{x∈C_{t}} α_{t}(x) cosh(β(s_{t−1,j} + x_{j})) =

= ∑_{j=1}^{m} [exp(βs_{t−1,j}) ; 2 ∑_{x∈C_{t}} α_{t}(x)e^{βx_{j}} + exp(−βs_{t−1,j}) ; 2 ∑_{x∈C_{t}} α_{t}(x)e^{−βx_{j}}] .

Hoeffding egyenlőtlenségének bizonyításában látotthoz (36) hasonlóan látható, hogy

∑_{x∈C_{t}} α_{t}(x)e^{−βx_{j}} ≤ exp (β^{2} ; 2 ) ,

így

w_{t}(s_{t}) ≤ ∑_{j=1}^{m} [exp(βs_{t−1,j}) ; 2 exp (β^{2} ; 2 ) + exp(−βs_{t−1,j}) ; 2 exp (β^{2} ; 2 )] =

= exp (β^{2} ; 2 ) w_{t}(s_{t−1}).

Kezdetben s_{0} = 0, w_{t}(s_{0}) = m, így

exp(|βs_{t,j}|) ; 2 ≤ cosh(βs_{t,j}) ≤ ∑_{j=1}^{m} cosh(βs_{t,j}) ≤ m exp (β^{2}n ; 2) ,

|s_{t,j}| ≤ ln(2m) + β^{2}n/2 ; β = √2n ln(2m).

Az alsó korlátot nem igazoljuk, megtalálható [Sp2]-ban.

Ezeket a játékokat lehetne úgy általánosítani, hogy azt követeljük meg, hogy a trajektória ne menjen ki egy bizonyos halmazból. Ha bennemarad, akkor Bea nyer, ha kimegy, akkor Alíz. Persze ez a halmaz egy végtelen játék esetén nem lehet egy s norma által meghatározott gömb, ha a C_{i} ⊂ B_{s,m} választást megengedjük Alíznak, hisz az előbb látott eredményekből, és a normák ekvivalenciájából adódik, hogy a trajektória nem maradna korlátos. Felmerül a kérdés tehát, hogy bizonyos C_{i} halmazsorozatok esetén milyen halmazban tud bennemaradni a trajektória, illetve mely játékosnak mikor van nyerő stratégiája. Az előjelezési esetben erre Bárány Imre szép geometriai feltételt adott. A fejezetet tehát –bizonyítás nélkül– ezen tétellel zárjuk [Ba]. Itt a normák megfelelő sugarú gömbjei helyett tetszőleges halmazok lesznek megadva.

Legyen V ∈ ℝ^{m} nemüres halmaz.

Definíció 10.3. Egy T ⊂ ℝ^{m} halmazt V -zártnak nevezünk, ha t ∈ T és v ∈ V esetén t + v ∈ T vagy t − v ∈ T közül legalább az egyik fennáll. A V -zárt halmazok halmazát jelölje C(V).

Jelöljük [V, K, z]-vel azt az előjelezési játékot, melyben K ⊂ ℝ^{m}, z ∈ ℝ^{m}, az i lépésben Alíz választ egy z_{i} ∈ V vektort, Bea pedig egy ε_{i} ∈ {−1, +1} előjelet. Bea nyer, ha

z + ∑_{i=1}^{n} ε_{i}z_{i} ∈ K, ∀n ∈ ℕ,

különben veszít. A következő tételek kimondják, hogy mely esetekben kinek van nyerő stratégiája.

Tétel 10.4. Alíznak pontosan akkor van nyerő stratégiája a [V, K, z] játékban ha nem létezik olyan T ∈ C(V), melyre z ∈ T ⊂ K.

Tétel 10.5. Beának pontosan akkor van nyerő stratégiája a [V, K, z] játékban ha létezik olyan T ∈ C(V), melyre z ∈ T ⊂ K.

A fenti két tétel persze nem ekvivalens, hiszen nem véges játékról van szó. A második tétel esetében könnyű ellenőrizni, hogy ilyen halmaz ismerete esetén Bea tényleg tud jól játszani.

11 Útátpakolás újra

11.1 Martingálok alkalmazása

A kiegyensúlyozó játék és a neki megfelelő kiválasztási feladat vizsgálatakor az egyik esetben egy on-line a másik esetben nem on-line feladatról volt szó, de az egyes C_{i} halmazokról soha nem tudtunk mást, minthogy a B_{s,m} egységgömbbe esnek. A továbbiakban nem foglalkozunk a a normás megfogalmazásokkal, hiszen a legfőbb alkalmazás, az útátpakolási probléma szempontjából csak egyetlen végtelen norma szerű eset lesz az érdekes. Egy D ∈ ℝ^{m} vektorral definiálhatnánk egy olyan u normát, melyre

∥x∥_{u} = max_{i∈[m]} | x_{i} ; D_{i} | .

Az ℓ_{∞} norma vizsgálatával csak az összes élen rendelkezésre álló szabad kapaciás minimumát tekinthetnénk szabad kapacitásnak, ezért a nem-uniform kapacitás miatt egy ilyen u normára lenne szükségünk, melynek az egységgömbje egy tégla. De mint írtuk, a normás megfogalmazást ezentúl hanyagoljuk, mert így egyszerűbb lesz, másrészt az utak átpakolását reprezentáló vektorok nem ebben a normában lesznek kicsik.

Feltesszük, hogy előre ismert minden C_{i} halmaz, s feltesszük azt is, hogy bizonyos ritkasági tulajdonságot tudunk, tehát hogy a C_{i} halmazok i-től függően kisebb gömbökbe is beleférhetnek. Kérdés, hogy ezen esetben mennyivel adhatunk jobb becslést a játékoknál megismert súlyfüggvényes algoritmusnál. Korábban láttunk rá példákat, hogy a kiválasztási feladat miként általánosítása az előjelezési feladatnak, ezért elegendőnek tartjuk a továbbiakban az előjelezési feladatra való szorítkozást. Ezt nyilván azért tesszük mert Cobanyan lemmájának alkalmazásával a CVS, sorrendezési feladatra szeretnénk eredményeket kapni.

A klasszikus diszkrepanciás vagy előjelezési esetet gyakran valószínűségi módszerrel oldottuk meg, egyszerűen a várható értéktől való nagy eltérés valószínűségét korlátoztuk. Most azonban egy olyan előjelezés akarunk, melyben minden előjelezett részletösszeg kicsi. Szerencse, hogy a véletlenül előjelezett sorozat martingált alkot, s Hoeffding egyenlőtlenségének martingálos javításával (15.5 tétel) hasonló becsléseket adhatunk, mint korábban.

Tétel 11.1. Legyen D ∈ ℝ^{m} olyan vektor, melyre

2 ∑_{j=1}^{m} exp (−\begin{matrix}& 2D_{j}^{2} \\ ∑_{i=1}^{n} & (2z_{i,j}) & 2 \end{matrix} ) ≤ 1.

Ekkor az (1, 2, …, n) sorozat minden π = (π_{1}, π_{2}, …, π_{n}) permutációjára létezik ε_{1}^{π}, ε_{2}^{π}, …, ε_{n}^{π} ∈ {−1, +1} előjelezés, hogy minden t ∈ [n]-re

−D_{j} ≤ ∑_{k=1}^{t} ε_{k}^{π}z_{i_{k},j} ≤ D_{j}, 1 ≤ j ≤ m.

Proof. Tekintsük egy véletlen előjelezést, melyben

ℙ (E_{i} = 1) = 1 2, ℙ (E_{i} = −1) = 1 2.

Ekkor az S_{t} = ∑_{i=1}^{t} E_{i}z_{i}, t = 1, 2, …, n sorozat martingált alkot, így a 15.5 tétel alkal-

mazásával

ℙ ( max_{1≤t≤n} S_{t,j} > D_{j}) < exp (−\begin{matrix}2D_{j}^{2} \\ ∑ & {n \atop i=1} & (2z_{i,j}) & 2 \end{matrix} ) .

Tehát minden koordinátára megbecsülve a hibavalószínűséget

ℙ (∃j : max_{1≤t≤n} |S_{t,j}| > D_{j}) ≤

≤ ∑_{j=1}^{m} ℙ ( max_{1≤t≤n} S_{t,j} > D_{j}) + ∑_{j=1}^{m} ℙ ( min_{1≤t≤n} S_{t,j} < −D_{j}) <

< 2 ∑_{j=1}^{m} exp (−\begin{matrix}& 2D_{j}^{2} \\ ∑_{i=1}^{n} & (2z_{i,j}) & 2 \end{matrix} ) ≤ 1.

Tehát létezik megfelelő előjelezés. A bizonyítás ugyanígy működik a vektorsorozat minden permutációjára.

Hatékony randomizált algoritmust kaphatunk kicsit gyengébb D ∈ ℝ^{m} korláttal, ha teljesül

2 ∑_{j=1}^{m} exp (−\begin{matrix}& 2D_{j}^{2} \\ ∑_{i=1}^{n} & (2z_{i,j}) & 2 \end{matrix} ) ≤ 1 2.

Ekkor a rossz esemény valószínűsége kisebb mint 1 2. Tekintsük azt az egyszerű eljárást, melyben minden lépésben mintát veszünk az E_{k} (k ∈ [n]) valószínűségi változókból. l lépés után a valószínűség, hogy nem kapunk jó előjelezést, kisebb mint 2^{−l}.

Hogy lássuk, mit jelent ez az állítás, érdemes megfogalmazni a következőt.

Következmény 11.2. Legyen D ∈ ℝ^{m} amire

D_{j} ≤ ; ; ; √2 ∑_{i=1}^{n} (z_{i,j})^{2} ln(2m) 1 ≤ j ≤ m.

Ekkor minden π = (π_{1}, π_{2}, …, π_{n}) permutációra létezik ε_{1}^{π}, ε_{2}^{π}, …, ε_{n}^{π} ∈ {−1, +1}, hogy minden 1 ∈ [t]-re

−D_{j} ≤ ∑_{k=1}^{t} ε_{k}^{π}z_{i_{k},j} ≤ D_{j}, 1 ≤ j ≤ m.

Speciálisan a z_{i} ∈ B_{ℓ_{∞},m} esetben visszakapjuk a √2n ln(2m) korlátot.

11.2 A dinamikus eset derandomizációja és martingálok

A valószínűségi módszer garantálta megfelelő előjelezés létezését. Az alkalmazás szempontjából nyilván jó lenne olyan algoritmust látni, mely kiszámol egy ilyet. Nyilvánvaló, hogy megint a feltételes valószínűségek módszerét hívjuk segítségül, s egyre kisebb feltételes valószínűségi mezőkben rendre lerögzítjük az előjeleket. Tegyük fel, hogy D és z_{1}, z_{2}, …, z_{n} kielégítik a 11.1 tétel feltételeit.

Legyen ℙ_{k} (ε_{1}, ε_{2}, …, ε_{k}) a hiba feltételes valószínűsége azon feltétel mellett, hogy az első k előjel ε_{1}, ε_{2}, …, ε_{k}.

ℙ_{k} (ε_{1}, ε_{2}, …, ε_{k}) = ℙ (∃j : max_{1≤t≤n} |S_{t,j}| > D_{j} | E_{1} = ε_{1}, …, E_{k} = ε_{k}) .

Ekkor

ℙ_{k} (ε_{1}, ε_{2}, …, ε_{k}) = 1 2ℙ_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, +1) + 1 2ℙ_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, −1) ,

tehát

ℙ_{k} (ε_{1}, ε_{2}, …, ε_{k}) ≥ min [ℙ_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, +1) , ℙ_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, −1)] .

Ha ki tudjuk számolni ezeket a feltételes valószínűségeket lépésről lépésre, kaphatunk egy nemnövekvő sorozatot. Minthogy 1 > ℙ_{0},

1 > ℙ_{0} ≥ ℙ_{1} (ε_{1}) ≥ ℙ_{2} (ε_{1}, ε_{2}) ≥ ⋯ ≥ ℙ_{n} (ε_{1}, ε_{2}, …, ε_{n}) .

Az utolsó feltételes valószínűség, –mivel ott már semmilyen véletlen nincs–, lehet 0 vagy 1, így 0. Tehát kaptunk egy jó előjelezést. Csak ki kell számolni rendre a feltételes valószínűségeket a döntési fa mentén, s ezzel az eljárással egy nagyon erős eszköz fog rendelkezésünkre állni az előjelezés kiszámításához.

A baj, hogy ezek a feltételes valószínűségek így közvetlenül nem számolhatóak ki hatékonyan, ezért a már korábban emlegetett Raghavan által bevezetett pesszimista becslést (pessimistic estimators) fogunk alkalmazni [Ra]. Raghavan ezt a MIP kapcsán vizsgált kiválasztási problémára vezette be, aminek igen közeli rokrona az előjelezési feladat. Itt azonban arra kell figyelnünk, hogy minden előjelezett kezdőszelet kicsi legyen, és az erre való kiterjeszthetőség azon fog múlni, hogy egy nulla várható értékű független valószínűségi változók összegeként kapott sorozat kezdőszeletei martingált alkotnak, s ez fennmarad az első valószínűségi változó lerögzítésével kapott feltételes mezőben is. De más változót, mondjuk a harmadikat nem rögzíthatjük le csak úgy, mert elromlana a martingál tulajdonság. Míg Raghavan eredeti feladatában tetszőleges sorrendben lerögzíthette a valószínűségi változók értékeit, nekünk már szigorúan követnünk kell majd azt a sorrendet, melyben a kezdőszeleteket akarjuk képezni.

Olyan pesszimista becslő U_{k} (ε_{1}, ε_{2}, …, ε_{k}) függvényeket fogunk bevezetni, melyre

1 ≥ U_{0}.  (24)

U_{k} (ε_{1}, ε_{2}, …, ε_{k}) = 1 2U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, +1) + 1 2U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, −1) , (25)

és „a jól választott” ε_{1}, ε_{2}, …, ε_{k−1} ∈ {−1, +1}, és tetszőleges ε_{k} ∈ {−1, +1} esetén

U_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}) > ℙ_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}) ,  (26)

Legyen

h_{j} = \begin{aligned}& 4D_{j} \\ ∑_{i=1}^{n} & (2z_{i,j}) & 2 \end{aligned} ,

a megfelelő konstans Hoeffding egyenlőtlenségének (15.5 tétel) bizonyításából. A pesszimista becslést a 15.5 tétel bizonyításában szereplő várható érték helyett vett feltételes várható értékekként kapjuk, a következő alakban:

U_{k} (ε_{1}, ε_{2}, …, ε_{k}) =  (27)

= ∑_{j=1}^{m} 𝔼 (e^{h_{j}(S_{n,j}−D_{j})} | E_{1} = ε_{1}, …, E_{k} = ε_{k}) +

+ ∑_{j=1}^{m} 𝔼 (e^{h_{j}(−S_{n,j}−D_{j})} | E_{1} = ε_{1}, …, E_{k} = ε_{k}) .

Ezek már hatékonyan számolható függvények, amennyiben jól tudunk számolni exponenseket. Amennyiben ez nincs így, közelítő becslő függvényeket vehetünk az exponensek becslésével, a dolgozatnak ez a vizsgálat azonban nem célja. Az előjeleket adó valószínűségi változók függetlenek, így a feltételek elintézése után kapott várható értékek szorzatra bomlanak, így hatékonyan számolhatóak.

𝔼 (exp (h_{j}S_{n,j} − h_{j}D_{j}) | E_{1} = ε_{1}, …, E_{k} = ε_{k}) =

= e^{−h_{j}D_{j}} exp (∑_{i=1}^{k} h_{j}ε_{i}z_{i,j}) ∏_{i=k+1}^{n} 𝔼 (e^{h_{j}E_{i}z_{i,j}}) .

A korábbiakhoz hasonlóan a teljes várható érték tétele miatt

U_{k} (ε_{1}, ε_{2}, …, ε_{k}) = 1 2U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, +1) + 1 2U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, −1) ,

tehát

U_{k} (ε_{1}, ε_{2}, …, ε_{k}) ≥ min [U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, +1) , U_{k+1} (ε_{1}, ε_{2}, …, ε_{k}, −1)] . (28)

Most már vázolhatjuk az algoritmusunkat. A k lépésben E_{k} értékét rögzítjük. Miután az első k − 1 lépésben ε_{1}, ε_{2}, …, ε_{k−1} értékkel rögzítettük k − 1 változó értékét, (28) miatt választhatjuk ε_{k}-t úgy, hogy minimalizáljuk az U_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}), pesszimista becslő függvényt, s így

U_{k−1} (ε_{1}, ε_{2}, …, ε_{k−1}) ≥ U_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}) .

Az algoritmus megkonstruál egy nemnövekvő sorozatot ezen függvények értékeiből. Azt kell igazolnunk, hogy az így lerögzített ε-ok kielégítik a (26)-ben megkövetelt feltételeket, s így ezek a pesszimista becslések valóban felső becslések a feltételes hibavalószínűségekre, s a fenti módon választott előjelezés jó lesz.

Tétel 11.3. A 11.1 tétel feltételei mellett a (27) függvény kielégíti a pesszimista becslő függvénytől elvárt (24)-(25)-(26) feltételeket az algoritmus szerint választott ε-okkal, s így az algoritmus meghatározza az előjelezési feladat egy jó megoldását. Még másképp fogalmazva k lépés után az

|∑_{i=1}^{l} ε_{i}z_{i,j}| ≤ D_{j}, j ∈ [m] , l ∈ [k]

egyenlőtlenségek mindegyike fennáll.

Proof. k-ra való indukcióval bizonyítunk. Kezdetben k = 0, nincs rögzített együttható, so the statement can be seen similarly as in the proof of theorem 11.1. k ≥ 1 esetén tegyük fel, hogy az első k−1 ≥ 0 együtthatót már lerögzítettük ε_{1}, ε_{2}, …, ε_{k−1} értékekre az algoritmus szerint. Ekkor tetszőleges ε_{k} ∈ {−1, +1} esetén

ℙ ( max_{1≤t≤n} S_{t,j} > D_{j} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) =

(mivel az első k − 1 együttható már jó)

= ℙ ( max_{k≤t≤n} S_{t,j} > D_{j} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) =

= ℙ (∑_{i=1}^{k} ε_{i}z_{i,j} + max_{k≤t≤n} ∑_{k+1≤i≤t} E_{i}z_{i,j} > D_{j}) =

= ℙ ( max_{k≤t≤n} exp (h_{j} ∑_{i=1}^{k} ε_{i}z_{i,j} + h_{j} ∑_{k+1≤i≤t}^{n} E_{i}z_{i,j}) > e^{h_{j}D_{j}} ) .

A

∑_{i=1}^{k} ε_{i}z_{i}, ∑_{i=1}^{k} ε_{i}z_{i} + E_{k+1}z_{k+1}, …, ∑_{i=1}^{k} ε_{i}z_{i} + ∑_{i=k+1}^{n} E_{i}z_{i}

sorozat martingál, így a koordinátasorozatai is. Most a Doob-egyenlőtlenséget (15.4 tétel) alkalmazva a megfelelő koordinátasorozatra

ℙ ( max_{k≤t≤n} exp (h_{j} ∑_{i=1}^{k} ε_{i}z_{i,j} + h_{j} ∑_{k+1≤i≤t} E_{i}z_{i,j}) > e^{h_{j}D_{j}} ) <

< 𝔼 exp (h_{j} ∑_{i=1}^{k} ε_{i}z_{i,j} + h_{j} ∑_{k+1≤i≤t} E_{i}z_{i,j} − h_{j}D_{j}) =

= 𝔼 (e^{h_{j}(S_{n,j}−D_{j})} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) ,

Hasonlóan

ℙ ( max_{1≤t≤n} −S_{t,j} > D_{j} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) <

< 𝔼 (e^{h_{j}(−S_{n,j}−D_{j})} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) .

Ezek összegéből

∑_{j=1}^{m} ℙ ( max_{1≤t≤n} |S_{t,j}| > D_{j} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) <

< U_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}) .

Tehát a (26) feltétel teljesül az algoritmus szerint választott ε_{1}, ε_{2}, …, ε_{k−1} mellett. Most rögzítsük ε_{k}-t +1 vagy −1-re, az algoritmusnak megfelelően. Ekkor

U_{k−1} (ε_{1}, ε_{2}, …, ε_{k−2}, ε_{k−1}) ≥ U_{k} (ε_{1}, ε_{2}, …, ε_{k−1}, ε_{k}) ,

tehát

1 ≥ U_{0} ≥ U_{1} (ε_{1}) ≥ ⋯ ≥ U_{k} (ε_{1}, ε_{2}, …, ε_{k}) >

> ∑_{j=1}^{m} ℙ ( max_{1≤t≤n} |S_{t,j}| > D_{j} | E_{1} = ε_{1}, E_{2} = ε_{2}, …, E_{k−1} = ε_{k−1}, E_{k} = ε_{k}) .

Az indukció miatt

max_{1≤t≤k−1} |∑_{i=1}^{t} ε_{i}z_{i,j}| ≤ D_{j}, ∀j ∈ [m] .

Ha a

|∑_{i=1}^{k} ε_{i}z_{i,j}| > D_{j}, j ∈ [m]

egyenlőtlenségek közül legalább egy fennállna, a megfelelő tag a jobboldalon 1 lenne. Tehát egy sem áll fenn közülük.

Az algoritmus tehát egy jó előjelezést ad.

11.3 Következmények az útátpakoláshoz szükséges kapacitásra

Nézzük most meg, hogy milyen következményei vannak az eddig bizonyított eredményeknek az útátpakolási problémára. Korábbi feltevésünk szerint csak azon esettel foglalkozunk, ahol a kezdeti és a végső használata a hálózatnak azonos, L, így 0 összegű vektorokat összegzünk. A szabad kapacitást pedig R(e)-vel jelöljük az e élen. Első triviális becslésünkben láttuk, hogy kétszeres kapacitásfüggvény (c = 2L) mellett tetszőleges átpakolási sorrend jó. Persze nem várhatjuk el, hogy az útátpakolás megoldhatóságáért a hálózatban csak a rendelkezésre álló kapacitás felét használhassák.

Az approximációs algoritmusok hatékonyságát általában approximációs faktorban mérik, nekünk itt az additív vizsgálat gyümölcsözőbb lesz. Legelső vizsgálatunkból, Grinberg és Sevastyanov sorrendezési tételéből (4.6 tétel) adódik a következő eredmény, amely csak hálózatban levő élek m számától és a maximális igénytől teszi függővé a szükséges szabad kapacitást.

Következmény 11.4. Az e élen az L(e) kapacitást legalább

c(e) ≥ L(e) + md_{max}

kapacitásra növelve minden e élen Sevastyanov és Grinberg algoritmusával determinisztikus polinomidőben meghatározható egy jó sorrendezés, ahol d_{max} a maximális igényt jelöli.

Láttuk, hogy további olyan eredményeink ℓ_{∞} normában nincsenek, melyek csak a dimenziótól függenének, az átpakolandó vektorok n száma is fontos lesz. A játékoknál vizsgáltuk Spencer súlyfüggvényes algoritmusának egy formális általánosítását (10.2 tétel), a következő eredményhez viszont csak az előjelezési esetre kimondott tétel is elég.

Következmény 11.5. Ha az L(e) kapacitást az e élen megnöveljük, úgy, hogy

c(e) ≥ L(e) + √2n ln(2m)d_{max} + εL(e), ∀e ∈ E(G),

akkor O(nm log(ε^{−1})) időben meghatározható egy jó sorrend.

Proof. A kívánt permutációt Chobanyan lemmája algoritmikus alakjának alkalmazásával számoljuk ki, melyben Spencer súlyfüggvényes algoritmusát alkalmazzuk szubrutinként. Kezdjünk egy tetszőleges π^{(0)} permutációval. Ez c(e) = 2L(e) szabad kapacitással megoldja a feladatot. A 4.4 tétel sterint a t. lépésben kapott π^{(t)} permutáció

R^{(t)}(e) ≥ √2n ln(2m)d_{max} + 2^{−t} (2L(e) − √2n ln(2m)d_{max})

szabad kapacitással megoldja a feladatot.

Bár nem látszik azonnal ez mekkora az előzőhöz képest, a távközlési hálózatok néhány tipikus tulajdonságát felhasználva ezt megbecsülhetjük. Nem túl meglepően feltehető, hogy m = |E| ≥ |V |, és hogy bármely két pont között pontosan egy igény van,

azaz n ≤ (\begin{matrix}|V | \\ 2 \end{matrix}) ≤ m^{2} ; 2 , tehát a log és konstans faktortól eltekintve ugyanazt a becslést

kaptunk.

A pesszimista becslésen alapuló derandomizációt azért keszítettük, hogy ezt a következményt megjavítsuk abban az esetben, ha az igények különbözőek, illetve egy-egy élet n-nél sokkal kevesebb út használ, (vagy lehet, hogy sok használ, de keveset kell közülük átpakolni). Spencer tétele helyett a mi derandomizációnkat követve az előző érvelést alkalmazva azonnal adódik, hogy t lépésben kiszámítható egy π^{(t)} permutáció, amely

c(e) ≥ L(e) + ; ; ; √2 ∑_{i=1}^{n} d_{i}^{2} ln(2m) + 2^{−t} (2L(e) − ; ; ; √2 ∑_{i=1}^{n} d_{i}^{2} ln(2m))

kapacitással megoldja a feladatot. Ami ezen még javíthat, hogy csak az átpakolandó vektorokra figyelünk, s csak azon élekre melyeken valóban átpakolunk.

Következmény 11.6. Az (1) jelölést használva

c(e) ≥ L(e) + ; ; ; √2 ∑_{i=1}^{n} v_{i}(e)^{2} ln(2m) + 2^{−t} (2L(e) − ; ; ; √2 ∑_{i=1}^{n} v_{i}(e)^{2} ln(2m)) ,

∀e ∈ E(G) esetén determinisztikus polinomidőben meghatározható egy jó sorrendezés.

Talán szemléletesebb, hogy mit jelent ez egységnyi, uniform igények esetén. Legyen tehát d_{i} = 1, i ∈ [n]. T (e)-vel jelölve az e élen azon i útpárok számát, ahol e a P_{i} és Q_{i} utak pontosan egyikében szerepel, magyarul az e élen átpakolandó utakat. Legyen T = max_{e} T (e). Ekkor a

c(e) ≥ L(e) + √2T (e) ln(2m) + 2^{−t} (2L(e) − √2T (e) ln(2m))

összefüggést kapjuk. Nyilván T (e) ≤ 2L(e), hiszen az e élen legfeljebb anni utat kell átpakolni, mint ahány a két útrendserben együtt átmegy rajta. Ebből a következőt kapjuk.

Következmény 11.7. Azonos, d_{i} = 1, i ∈ [n] nagyságú igények esetén ha az L(e) kapacitást az e élen megnöveljük, úgy, hogy

c(e) ≥ L(e) + √4L(e) ln(2m) + εL(e), ∀e ∈ E(G),

akkor O(nm log(ε^{−1})) időben meghatározlató egy jó sorrend.

Ez azt jelenti, hogy tetszőleges hálózatnál, ha egy élet jó sok út használ a P, és Q útrendszerekben, akkor a kapacitást ehhez képest csak kicsivel kell megnövelni. Így nagy L(e)-kre approximációs faktorban nagyon jó közelítés kapható.

Most adjunk még egy cseppnyi esélyt egy további javítási lehetőségnek. Gondoljunk bele még egyszer, hogy ezt az eredményt úgy kaptuk, hogy az előjelezés előállításához minden egyes élre korlátoztuk a két rossz esemény valószínűségét külön-külön kisebb mint 1 ; 2m-re. Ha a rossz események kevés másikkal vannak összefüggésben, akkor a Lovász Local Lemma [EL] segítséget jelenthet jobb korlát elérésében. Tegyük fel, hogy az átpakolandó utak mind legfeljebb D hosszúak. Ekkor az átpakolást adó vektorokban legfeljebb 2D nemnulla elem van. Felírhatunk tehát egy olyan függőségi gráfot, melyben minden minden fok legfeljebb 2(2DT). A LLL alkalmazásával az 1 ; 2m „hibavalószínűség” 1 ; e2(2DT)-re cserélhető, amivel kaphatunk egy jobb garanciát ritka esetben. A hálózatos feladatokban gyakran nagyon rövid utak szerepelnek, így érdemes ilyen vizsgálatokba belemenni. Itt azonban az algoritmussal komoly probléma merül fel. Még a derandomizáció előtt az LLL-erősítés nélküli korlátainkra láttuk, hogy kis veszteséggel kaphatunk hatékony randomizált algoritmust. Itt még az sem ismert, és így determinisztikus, derandomizált algoritmus pláne nem. A klasszikus diszkrepanciakérdésnel ez a derandomizáció lényegében megoldható, az áttörést Beck József műve hozta, melyben hipergráf 2-szinezhetőségére illetve hipergráf diszkrepanciájára vizsgálta a derandomizáció lehetőségét ([Be]), Alon pedig ennek párhuzamosíthatóságával foglalkozott ([Al]). Beck LLL derandomizációjában a valószínűségi változók értékei rögzítésének sorrendjét nem határozza meg előre, nem is lehet, nálunk pedig a martingál tulajdonság fennmaradásához fontos volt a rögzítési sorrend. A téma vizsgálata során nem jutott tudomásunkra, hogy ezt eddig valaki megoldotta volna.

Nyitott kérdés 11.8. Hogyan lehet derandomizálni az LLL-erősített esetet?

Még egy talán az alkalmazások szempontjából már nem annyira érdekes kérdés felvetődik. A kezdőszeletek egy speciális lamináris rendszert alkotnak. Vegyünk most egy tetszőleges F lamináris rendszert [n]-en. Kiterjeszthető-e az egzisztenciatétel (11.1 tétel), illetve a derandomizáció ugyanilyen korlátokkal arra az esetre, amikor olyan ε előjelezést keresünk, hogy a ∑_{i∈F} ε_{i}z_{i}, F ∈ F vektorok mind kicsik legyenek.

12 Mohó heurisztikák és a véletlen sorrend

Az RSP megoldására kifejlesztettünk mohó heurisztikákat is. Tekintsünk súlyfüggvényeket a permutációk jóságának mérésére. A heurisztikus algoritmusaink ekkor a következőképpen működnek. Az r. lépésben, amikor π_{1}, π_{2}, …, π_{r−1} már rögzített, π_{r}-et az f_{r}(π_{1}, π_{2}, …, π_{r−1}, π_{r}), súlyfüggvény minimalizálásával választjuk, azzal a feltétellel, hogy az átpakolandó igényeket visszatevés nélkül kell választani, azaz hogy π_{1}, π_{2}, …, π_{r−1}, π_{r} permutáció kezdete lehessen. Egy ilyen súlyfüggvénnyel a kapacitás sértését mérjük, és minimalizáljuk, vagy maximalizáljuk a szabad kapacitást, stb. Különböző súlyfüggvények különböző viselkedésű heurisztikákat adnak. Most, hogy ezen heurisztikák működését összehasonltsuk a véletlen permutáció viselkedésével, ez utóbbit fogjuk vizsgálni.

Tekintsünk egy Π_{1}, Π_{2}, …, Π_{n} véletlen permutációt, legyen ez az átpakolási sorrend. (Minden permutáció ugyanazon 1 ; n! valószínűséggel szerepel.) Ez modellezhető azon folyamattal, amikor minden lépésben kiveszünk egy átpakolandó utat az összes igény urnájából, visszatevés nélkül. Definiáljuk a X_{i} = v_{Π_{i}}, i ∈ [n] valószínűségi változókat. Definiáljuk továbbá az Y_{i}, i ∈ [n] valószínűségi változókat is, ahol Y_{i}-t az {v_{1}, v_{2}, …, v_{n}} univerzumból mintázzuk, visszatevéssel. Vegyük észre, hogy 𝔼Y_{i} = 0 ∈ ℝ^{m}. Ekkor segtségül hívhatjuk Hoeffding egy tételét, mely jelen esetben a következő alakban fogalmazható újra.

Tétel 12.1. [Hoe] A folytonos, konvex g : ℝ → ℝ függvénnyel

𝔼g (∑_{i=1}^{t} X_{i,j}) ≤ 𝔼g (∑_{i=1}^{t} Y_{i,j}) ,

ahol t ∈ [n], j ∈ [m].

Ezen tétel segítségével korlátozhatjuk a valószínűségét olyan valószínűségi változók össegének várható értékétől való nagy eltérését, melyeket visszatevés nélkül mintáztunk valamely univerzumból. Exponenciális függvénnyel alkalmazva, és a 15.1 tétellel korlát kapható a véletlen permutáció nagy eltéréseinek valószínűségére.

Tétel 12.2. Amennyiben

c(e) ≥ L(e) + √2n ln(nm)d_{max} ∀e ∈ E,

akkor létezik megoldása az RSP-nek, és egy ilyen determinisztikus ploinomidőben kiszámolható. A kicsit gyengébb

c(e) ≥ L(e) + √2n ln(2nm)d_{max} ∀e ∈ E,

korláttal, a véletlen sorrend legalább 1 2 valószínűséggel jó.

Ez a korlát gyengébb mint az előzőek, de a bizonyítási módszer modellezi a véletlen permutációt, a derandomizációja pedig modellezi a heurisztikus algoritmusunkat egy exponenciális súlyfüggvénnyel.

Proof. Tekintsük a véletlen permutációval fent definiált valószínűségi változókat. Legyen D_{j} = √2n ln(nm)d_{max}. Ekkor h_{t,j} = 4D_{j} ; 4td_{max}^{2} választással a Markov-egyenlőtlenség alkalmazásával, és a 15.1 tétellel

ℙ (∑_{i=1}^{t} X_{i,j} > D_{j}) = ℙ (exp (h_{t,j} ∑_{i=1}^{t} X_{i,j}) > e^{h_{t,j}D_{j}}) <

< e^{−h_{t,j}D_{j}}𝔼 exp (h_{t,j} ∑_{i=1}^{t} X_{i,j}) ≤ e^{−h_{t,j}D_{j}}𝔼 exp (h_{t,j} ∑_{i=1}^{t} Y_{i,j}) ≤

(a 15.1 tétel bizonyítása alapján, 𝔼Y_{i,j} = 0-t használva)

≤ exp (− 2D_{j}^{2} ; 4td_{max}^{2} ) ≤ exp (− 2D_{j}^{2} ; 4nd_{max}^{2} ) .

Tehát

ℙ (∃t ∈ [n], j ∈ [m] : ∑_{i=1}^{t} X_{i,j} > D_{j}) < nm exp (− 2D_{j}^{2} ; 4nd_{max}^{2} ) = 1.

A második rész igazolása ugyanaz, D_{j} = √2n ln(2nm)d_{max} választással, s ekkor a siker valószínűsége legalább 1 2 Ezt a véletlen választást iterálva hatékony randomizált algoritmus kapható.

A derandomizációban tekintsük a W_{r} súlyfüggvényt, ami valójában egy pesszimista becslő függvény.

W_{r} (π_{1}, π_{2}, …, π_{r}) =

∑_{j∈[m],t∈[n]} e^{−h_{t,j}D_{j}}𝔼 exp (h_{t,j} ∑_{i=1}^{t} X_{i,j} | Π_{1} = π_{1}, Π_{2} = π_{2}, …, Π_{r} = π_{r}) .

Kezdetben W_{0} ≤ 1, majd a korábban látott érvelés szerint, minimalizálva rendre r = 1, 2, …, n-re a W_{r} súlyfüggvényt, kaphatunk egy nemnövekvő sorozatot,

1 ≥ W_{0} ≥ W_{1}(π_{1}) ≥ W_{2}(π_{1}, π_{2}) ≥ ⋯ ≥ W_{n}(π_{1}, π_{2}, …, π_{n}) =

∑_{j∈[m],t∈[n]} e^{−h_{t,j}D_{j}}𝔼 (exp (h_{t,j} ∑_{i=1}^{t} X_{i,j}) | Π_{1} = π_{1}, Π_{2} = π_{2}, …, Π_{n} = π_{n}) .

Így

−D_{j} + ∑_{i=1}^{t} v_{π_{i}} ≤ 0, ∀j ∈ [m], t ∈ [n],

tehát az így választott permutáció eleme a 12.2 tétel állításában szereplő eseménynek.

13 Multi-color diszkrepanciák

A dolgozatban mindeddig egy vektorhalmaz kétfelé osztásának egyenletességét vizsgáltuk, ezután is ezt fogjuk tenni. Álljon itt egyetlen tétel, mely arról szól, hogy a kétfelé osztás lineáris diszkrepanciájának nagyságrendjével felülbecsülhető az r-felé osztás diszkrepanciája. További erdedmények a multi-color diszkrepanciákról [DoSr, Do]-ben olvashatók.

Tétel 13.1. ([BeFi]) Legyen z_{1}, z_{2}, …, z_{n} ∈ ℝ^{m}, és legyen ∥ · ∥ tetszőleges norma ℝ^{m} − en. Tegyük fel, hogy tetszőleges α_{1}, α_{2}, …, α_{n} ∈ [0, 1] esetén létezik δ_{1}, δ_{2}, …, δ_{n} ∈ {0, 1} kerekítés, hogy

∥∑_{i=1}^{n}(α_{i} − δ_{i})z_{i}∥ ≤ D.

Ekkor létezik olyan N_{1}, N_{2}, …, N_{r} partíciója az [n] halmaznak, hogy tetszőleges j ∈ [r]-re

∥ ∑_{i∈N_{j}} z_{i} − 1 ; r ∑_{i=1}^{n} z_{i}∥ ≤ (3 − 2 ; r − 1) D.

Proof. r-re való indukcióval bizonyítunk. r=2-re a feltételből tudjuk. Legyen r>2, és tegyük fel, hogy az állítás már igaz 2 ≤ r′ ≤ r − 1 esetén. Legyen γ_{r} = 3 − 2 ; r−1. Legyen r′ = ⌈ r ; 2⌉. A feltétel miatt létezik A, B partíciója [n]-nek, hogy Ekkor

∥∑_{i∈A} z_{i} − r′ ; r ∑_{i=1}^{n} z_{i}∥ ≤ D

és

∥∑_{i∈B} z_{i} − r − r′ ; r ∑_{i=1}^{n} z_{i}∥ ≤ D.

Mivel max{r′, r − r′} ≤ r − 1, az indukciós feltétel miatt létezik az A és B-beli indexű vektoroknak r′ illetve r − r′ részű egyenletes partíciója N_{1}, N_{2}, …, N_{r′} illetve M_{1}, M_{2}, …, M_{r−r′} részekre, hogy

∥ ∑_{i∈N_{j}} z_{i} − 1 ; r′ ∑_{i∈A} z_{i}∥ ≤ Dγ_{r′},

ahol j ∈ [r′] és

∥ ∑_{i∈M_{j}} z_{i} − 1 ; r − r′ ∑_{i∈B} z_{i}∥ ≤ Dγ_{r−r′},

ahol j ∈ [r − r′]. Az tétel állításához elég ellenőrízni, hogy

max {γ_{r′} + 1 ; r′ , γ_{r−r′} + 1 ; r − r′ } ≤ γ_{r},

ez pedig egyszerű számolásból adódik.

14 Ütemezéselméleti alkalmazás:

korlátos vektorösszegzés a shop-ütemezésben

A következőekben megismerkedünk a CVS néhány ütemezéselméleti alkalmazásával, a shop feladatok területéről. Az eredmények nagyrészt a magyar nyelvű [BaFi] cikkből származnak. Definiálunk először egy általános feladatot, a G-feladatot, ami lényegében keretként szolgál, majd ennek specializálásával eljutunk klasszikus problémákhoz, így az open shop és flow shop feladatokhoz.

G-feladat. Adott n munka (job), és m különböző gép 1, 2, …, m-mel sorszámozva. A j munka r_{j} részfeladatot (operation) tartalmaz, ezek halmaza O_{j} = {o_{1}^{j}, o_{2}^{j}, …, o_{r_{j}}^{j}}. Az o_{i}^{j} részfeladat elvégzésének ideje t_{i}^{j}, és ez a feladat elvégezhető a gépek egy J_{i}^{j} ⊆ {1, 2, …, m} halmazából választott tetszőleges gépen. Minden egyes j munkára O_{j}-n definiált egy megelőzési reláció egy R_{j} irányított aciklikus gráffal (melynek ponthalmaza O_{j}). Az (o_{i}^{j}, o_{l}^{j}) él azt jelenti, hogy az o_{i}^{j} feladatot be kell fejezni mielőtt az o_{l}^{j} elvégzése megkezdődne. Feltesszük továbbá hogy a részfeladatok nem megszakíthatóak, egy gép egyszerre csak egy részfeladaton dolgozhat, és egy munkának egyszerre csak egy részfeladata végezhető. A cél egy olyan S ütemezés keresése, s_{i}^{j} ≥ 0 kezdési időkkel, ami minimalizálja az utoljára befejezett részfeladat befejezési idejét:

F (S) = max_{i,j}(s_{i}^{j} + t_{i}^{j}) → min .

A G-feladat jelöléseit használva már nagyon könnyű definiálni azokat a speciálisabb feladatokat, melyeket vizsgálni fogjuk. A továbbiakban feltesszük, hogy t_{i}^{j} ≤ 1.

FS (flow shop). r_{j} = m, R_{j} = {(o_{k}^{j}, o_{k+1}^{j}), k = 1, 2, …, m − 1}, J_{i}^{j} = {i}, (j = 1, 2, …, n, i = 1, 2, …, m). Tehát minden munka részfeladatait ugyanazon előre adott sorrendben kell elvégezni, mégpedig rendre az 1, 2, …, m gépeken.

OS (open shop). A G-feladat speciális esete az r_{j} = m, R_{j} = ∅, J_{i}^{j} = {i}, (j = 1, 2, …, n, i = 1, 2, …, m). Magyarul nincs megkötés a részfeladatok sorrendjére.

Néhány jelölés. Az i gép összideje M_{i} = ∑_{j=1}^{n} t_{i}^{j}, a leghoszabb gép hossza pedig

M = max_{1≤i≤m} M_{i}, a j munka összideje L_{j} = ∑_{i=1}^{m} t_{i}^{j}, a leghoszabb munka hossza pedig

L = max_{1≤j≤n} L_{j}.

Tetszőleges S ütemezés F (S) átfutási idejére

F (S) ≥ max(M, L).  (29)

A következő OS-ra kimondott eredmény arról szól, hogy az optimum nem is lényegesen nagyobb ezen alsó becslésnél. A listás ütemezésben ha van rendelkezésre álló o_{i}^{j} részfeladat, tehát más gépeken nem fut o_{l}^{j} részfeladat, akkor azonnal felrakjuk az i gépre.

Tétel 14.1. (Racsmány Anna) Az OS feladatban listás S ütemezéssel

F (S) ≤ M + (m − 1).

Proof. Tekintsük azt az i gépet, mely utoljára fejezi be a munkát. Ezen a munkák sorrendje j_{1}, j_{2}, …, j_{n}. A j_{n} munka o_{i}^{j_{n}} részfeladatát azért nem lehetett elvégezni korábban mert más gépeken mindig futott valamely o_{l}^{j_{n}} részfeladat. Az állásidők összege tehát legfeljebb ∑_{l≠i} t_{l}^{j_{n}} ≤ m − 1, így

F (S) ≤ ∑_{j=1}^{n} t_{i}^{j} + (m − 1) ≤ M + (m − 1).

2 gép esetén elérhető olyan ütemezés, amelyre az átfutási idő egyezik a triviális (29) alsó becsléssel ([GoSa]), több gép esetén előfordulhat, hogy az optimum nagyobb. Az OS feladatnak azonban van egy olyan tulajdonsága, hogy ha a leghoszabb gép hossza elég nagy, akkor az optimális ütemezés hossza ennyi. Mi minthogy a CVS az egyik fő témánk, a következő tételt igalzonjuk.

Tétel 14.2. ([BaFi]) Ha M ≥ m^{2} + 2m − 1, akkor az optimális S ütemezésre

F (S) = M,

s egy ilyen ütemezés polinomidőben meghatározható Sevastyanov es Grinberg algoritmusával.

Proof. Nyújtsuk úgy meg a részfeladatokat, hogy t_{i}^{j} ≤ 1 továbbra is fennálljon, és

minden gépnek ugyanannyit kelljen dolgoznia, ∑_{j=1}^{n} t_{i}^{j} = M legyen. Ezt megtehetjük, s

a módosított időkkel kapott ütemezés megengedett ütemezés lesz az eredeti feladatra is, ugyanolyan átfutási időkkel. Az idők meghoszabbítása után olyan ütemezést kell konstruálni, melyben minden gép folyamatosan dolgozik, hisz csak így érhető el a kívánt korlát. Tekintsük a

v^{j} = ( t_{1}^{j} − t_{2}^{j} ; t_{2}^{j} − t_{3}^{j} ; ⋮ ; t_{m−1}^{j} − t_{m}^{j} ; t_{m}^{j} − t_{1}^{j}) , j ∈ [n]

vektorokat a munkákhoz, majd alkalmazzuk a 4.6 tétel algoritmusát. Az egyszerűbb jelölés kedvéért indexeljük át a munkákat, úgy hogy az új sorrend (1, 2, …, n) legyen. Ekkor

∑_{l=1}^{k} t_{i}^{l} − ∑_{l=1}^{k} t_{i+1}^{l} ≤ m,

∑_{l=1}^{k} t_{m}^{l} − ∑_{l=1}^{k} t_{1}^{l} ≤ m.

Az első gépen (1, 2, …, n) lesz a sorrend, a többin pedig ennek ciklikus eltolásából kapunk egy sorrendet úgy, hogy az azonos munkához tartozó részfeladatok ne essenek egy időbe. A részfeladatok sorrendje a gépeken a következő lesz, ahol sorok rendre az 1, 2, 3, …, m gépen levő sorrendet jelölik.

1,  2,  …  …, n
j_{2} + 1, j_{2} + 2, …, n, 1,  …, j_{2}
j_{3} + 1, j_{3} + 2, …  …, n, 1  …, j_{3}
⋮  ⋮
j_{m} + 1, j_{m} + 2, …  …, n, 1, …, j_{m}

Az j_{1} = 0, j_{2}, j_{3}, …, j_{m} indexeket később rekurzívan definiáljuk. Az első munka részfeladatainak kezdési idejei az i gépen

s_{i}^{1} = ∑_{k=j_{i}+1}^{n} t_{i}^{k}.

Most definiáljuk az s_{i}^{j} kezdési időket. A további kezdési idők logikusan definiálhatók az alapján, hogy hogy néznek ki a sorrendek,

s_{i}^{j} = \begin{cases}s_{i}^{1} + ∑_{k=1}^{j−1} t_{i}^{k} & ha j ≤ j_{i}, \\ ∑_{k=j_{i}+1}^{j−1} t_{i}^{k} & ha j > j_{i}. \end{cases}

Ekkor logikusan definiálva j_{2}-t, ez legyen a legkisebb index, melyre

∑_{k=j_{2}+1}^{n} t_{i}^{k} ≥ m + 1.  (30)

Hasonlóan, ha j_{i}, s_{i}^{1} már definiált, akkor legyen j_{i+1} az a legnagyobb index, melyre

(s_{i+1}^{1} =) ∑_{k=j_{i+1}+1}^{n} t_{i+1}^{k} ≥ s_{i}^{1} + (m + 1).  (31)

Ekkor s_{i}^{1} ≤ s_{i−1}^{1} + (m + 2), így

M ≥ m^{2} + 2m − 1 = (m − 1)(m + 2) + (m + 1) ≥ s_{m}^{1} + (m + 1),  (32)

tehát a j_{i} indexek definiáltak. Most belátjuk, hogy a j munka részfeladatai nem ütköznek egymással. Ha j ≤ j_{i}, akkor az i gépen az o_{i}^{j} részfeladat az o_{i}^{1} után kerül az i gépre (vagy ő maga o_{i}^{1}), ezekre a j munkákra azt kell látni, hogy

s_{i}^{j} ≥ s_{i−1}^{j} + t_{i−1}^{j},  (33)

ezt pedig a következőképpen lehet

s_{i}^{j} − s_{i−1}^{j} = s_{i}^{1} + ∑_{k=1}^{j−1} t_{i}^{k} − (s_{i−1}^{1} + ∑_{k=1}^{j−1} t_{i−1}^{k}) =

= s_{i}^{1} − s_{i−1}^{1} + (∑_{k=1}^{j−1} t_{i−1}^{k} − ∑_{k=1}^{j−1} t_{i}^{k}) ≥ (m + 1) − m ≥ t_{i−1}^{j}.

Ha a j munkának minden o_{i}^{j} részfeladata ilyen, akkor kész vagyunk, ha nem, akkor a többi részfeladatra j > j_{i}, és az o_{i}^{j} részfeladat az o_{i}^{1} előtt kerül végrehajtásra. Ezt azzal is jellemezhetnénk, hogy

s_{i}^{1} + ∑_{k=1}^{j} t_{i}^{j} > M.

Ezekre az kell, hogy

s_{i+1}^{j} ≥ s_{i}^{j} + t_{i}^{j},  (34)

illetve

s_{1}^{j} ≥ s_{m}^{j} + t_{m}^{j}.  (35)

(34)-hez

s_{i+1}^{j} − s_{i}^{j} = s_{i+1}^{1} − ∑_{k=j}^{n} t_{i+1}^{k} − (s_{i}^{1} − ∑_{k=j}^{n} t_{i}^{k}) =

= s_{i+1}^{1} − s_{i}^{1} + ∑_{k=1}^{j−1} t_{i+1}^{k} − ∑_{k=1}^{j−1} t_{i}^{k} ≥ (m + 1) − m ≥ t_{i}^{j}.

(35)-hez

s_{m}^{j} = ∑_{k=j_{m}+1}^{j−1} t_{m}^{k} = ∑_{k=j_{m}+1}^{j−1} t_{m}^{k} + (s_{m}^{1} + ∑_{k=1}^{j_{m}} t_{m}^{k} − M) =

= s_{m}^{1} − M + ∑_{k=1}^{j−1} t_{m}^{k} ≤ s_{m}^{1} − M + ∑_{k=1}^{j−1} t_{1}^{k} − m ≤

≤ ∑_{k=1}^{j−1} t_{1}^{k} − 1 = s_{1}^{j} − 1 ≤ s_{1}^{j} − t_{m}^{j},

(32) felhasználásával.

A 14.2 tétel feltétele javítható, mégpedig M = Ω(m ln m) is elég, de ez bonyolultabb megfontolásokat igényel, itt nem célunk igazolni [BaFi]. Jó áttekintést kaphatunk a shop-ütemezésben alkalmazott CVS és egyéb geometriai módszerekről a [Se1] összefoglalásból.

Most rátérünk az FS feladat egy hasonló tételére, melyben a bizonyítás az előzőhöz hasonló, a tétel Racsmány Anna állításához hasonlóan arról szól, hogy a létezik ütemezés a triviális becsléstől nem messze eső optimummal, a bizonyítás viszont nem olyan triviális és CVS-technikát használ.

Tétel 14.3. ([BaFi]) Az FS feladatnak létezik olyan permutáció típusú S ütemezése, melyre

(M ≤) F (S) ≤ M + m(m − 1),

és egy ilyen ütemezés polinomidőben meghatározható Sevastyanov es Grinberg algoritmusával.

Proof. A 14.2 tétel bizonyításában alkalmazotthoz hasonlóan nyújtsuk meg a részfela-

datokat, hogy t_{i}^{j} ≤ 1 továbbra is fennálljon, és ∑_{j=1}^{n} t_{i}^{j} = M legyen. Most legyen

v^{j} = ( t_{1}^{j} − t_{2}^{j} ; t_{2}^{j} − t_{3}^{j} ; ⋮ ; t_{m−2}^{j} − t_{m−1}^{j} ; t_{m}^{j−1} − t_{m}^{j}) ∈ ℝ^{m−1}, j ∈ [n]

vektorokat a munkákhoz, majd alkalmazzuk a 4.6 tétel algoritmusát. Az egyszerűbb jelölés kedvéért indexeljük át a munkákat, úgy hogy az új sorrend (1, 2, …, n) legyen. Most

∑_{l=1}^{k} t_{i}^{l} − ∑_{l=1}^{k} t_{i+1}^{l} ≤ m.

Minden gépen (1, 2, …, n) lesz a sorrend, csak a későbbi gépeken a részfeladatok elkezdését állásidő fogja megelőzni, viszont ha egy gépen már elkezdődött egy részfeladat, utána már nem lesz állásidő. Az első munka részfeladatainak kezdési idejei az i gépen

s_{i}^{1} = (i − 1)m.

Az ezt követő munkák részfeladatainak kezdési idejei pedig

s_{i}^{j} = s_{i}^{j−1} + t_{i}^{j−1}.

Azt kell csak igazolnunk, hogy ezen kezdési időkkel az egyazon munkához tartozó részmunkák végrahajtása nem ütközik. Nyilván nem meglepő, hogy a 14.2 tétel bizonyításában látott számoláshoz hasonlóan ez megtehető, nem részletezzük.

Egy dologra azonban érdemes felhívni a figyelmet. Bár a [BaFi] cikk ezt nem hangsúlyozza, a bizonyításban szereplő sorrendben csak arra volt szükség, hogy a trajektória koordinátái ne legyenek túl nagyok, de alsó korlátozásra nem volt szükség. Érdekes, hogy a másik alkalmazásban, az útátpakolásban, –valójában ez volt az egész dolgozat ötlete– , szintén csak erre van szükség. Érdemes lenne tehát ezen nemszimmetrikus esetek kutatására hangsúlyt fektetni. Sajnos a hasonló diszkrepanciaproblémákban gyakran előfordul, hogy a szimmetrikus esetek eredményei –legalábbis aszimptotikusan– élesen ismertek, de a nemszimmetrikus esetekkel nem áll ilyen jó helyen a kutatás. Így van ez például számtani sorozatok diszkrepanciáinak vizsgálatakor is.

A shop-ütemezés további részleteibe nem tisztünk belemenni, egyszerűen a CVS alkalmazhatósága miatt ez a rövid fejezet idekívánkozott. Ma a CVS helyett már az ú.n. nemszigorú vektorösszegzést (NVS) is kutatják, melyben a trajektóriának majdnem egy poliéderbe kell esnie, megteheti, hogy az egyik határoló lapon kilép, de ekkor a következő lépésben vissza kell lépnie. (Előfordulhat, hogy a trajektória soha nincs a poliéderben). A NVS alkalmazása is gyümölcsöző a shop-ütemezésben.

15 Függelék: néhány fontos egyenlőtlenség valószínűségszámításból

A függelékben a valószínűségi változók várható értékeiktől való nagy eltérésük valószínűségét korlátozó egyenlőtlenség közül sorolunk fel néhányat. Ezek azért szorulnak függelékbe, mert –bár gyakran használjuk őket–, olyan szorosan nem kapcsolódnak a témához.

Tétel 15.1. (W. Hoeffding, [Hoe]) Legyenek X_{1}, X_{2}, …, X_{n} független valószínűségi vál-

tozók, a_{i} ≤ X_{i} ≤ b_{i}, t > 0, S_{k} = ∑_{i=1}^{k} X_{i}. Ekkor

ℙ (S_{n} − μ > t) < exp (− 2t^{2} ; ∑_{i=1}^{n}(b_{i} − a_{i})^{2} ) .

A bizonyítást is vázoljuk, hiszen több olyan eredmény van benne, melyek máshol hasznosak lesznek.

Proof. Legyen μ_{i} = 𝔼X_{i}. Tetszőleges h > 0-ra az exponenciális függvény monotonitása, és például a Markov-egyenlőtlenség miatt

ℙ (S_{n} − 𝔼S_{n} > t) = ℙ (e^{h(S_{n}−𝔼S_{n})} > e^{ht}) <

< e^{−ht}𝔼 (e^{h(S_{n}−𝔼S_{n})}) = e^{−ht} ∏_{i=1}^{n} 𝔼 (e^{h(X_{i}−μ_{i})}) .

Az exponenciális függvény konvexitása miatt

e^{hX_{i}} ≤ b_{i} − X_{i} ; b_{i} − a_{i} e^{ha_{i}} + X_{i} − a_{i} ; b_{i} − a_{i} e^{hb_{i}},

𝔼e^{hX_{i}} ≤ b_{i} − 𝔼X_{i} ; b_{i} − a_{i} e^{ha_{i}} + 𝔼X_{i} − a_{i} ; b_{i} − a_{i} e^{hb_{i}}.

𝔼e^{h(X_{i}−μ_{i})} ≤ e^{−hμ_{i}} (b_{i} − μ_{i} ; b_{i} − a_{i} e^{ha_{i}} + μ_{i} − a_{i} ; b_{i} − a_{i} e^{hb_{i}}) = e^{L_{i}(h_{i})},

ahol L_{i}(h_{i}) = −hp_{i} + ln(1 − p_{i} + p_{i}e^{h_{i}}),

h_{i} = h(b_{i} − a_{i}), p_{i} = μ_{i} − a_{i} ; b_{i} − a_{i} .

Ekkor

L′_{i}(h_{i}) = −p_{i} + p_{i} ; (1 − p_{i})e^{−h_{i}} + p_{i} ,

L′′_{i}(h_{i}) = \begin{matrix}p_{i}(1 − p_{i}) \\ [(1 − p_{i})e^{−h_{i}} + p_{i}] & 2 \end{matrix} .

Ez utóbbi, mivel u(1 − u) alakú, ahol 0 < u < 1, legfeljebb 1 4. Most a Taylor-formula miatt a következőképpen becsülhetünk:

L_{i}(h_{i}) ≤ L(0) + L′(0)h_{i} + 1 8h_{i}^{2} = 1 8h^{2}(b_{i} − a_{i})^{2},

𝔼e^{h(X_{i}−μ_{i})} ≤ e^{1 8 h^{2}(b_{i}−a_{i})^{2}}.  (36)

Így

e^{−ht}𝔼 (e^{h(S_{n}−𝔼S_{n})}) ≤ exp (−ht + 1 8h^{2} ∑_{i=1}^{n}(b_{i} − a_{i})^{2}) .

A jobboldal a minimumát a

h = 4t ; ∑_{i=1}^{n}(b_{i} − a_{i})^{2}

helyen veszi fel, amit behelyettesítve kapjuk az állítást. Tétel 15.2. ([Ra]) Legyenek X_{1}, X_{2}, …, X_{n} független indikátor valószínűségi változók, a_{i} ∈ (0, 1], 𝔼 (X_{i}) = p_{i}. Legyen továbba X = ∑_{i=1}^{n} a_{i}X_{i}, 𝔼X = μ. Ekkor δ > 0 esetén

ℙ (X > (1 + δ)μ) < ( e^{δ} ; (1 + δ)^{(1+δ)} )^{μ} .

Az így kapott korlátra vezessük be a következő jelölést:

B(μ, δ) = ( e^{δ} ; (1 + δ)^{(1+δ)} )^{μ} .

Ez a függvény δ > 0-ra monoton csökken, így legyen

D(μ, p) = inf{δ > 0 : B(μ, δ) ≤ p},

azaz B(μ, D(μ, p)) = p.

Kis számolással igazolhatóak a következő összefüggések. Lemma 15.3. μ > ln 1 ; p esetén

D(μ, p) ≤ (e − 1)√\begin{matrix}ln & 1 ; p \\ μ \end{matrix} ,

μ ≤ ln 1 ; p esetén pedig

D(μ, p) ≤ e ln 1 ; p ; μ ln [ e ln 1 ; p ; μ ].

Igazolható továbbá, hogy 0 < μ_{1} ≤ μ_{2}, δ > 0 esetén

B (μ_{1}, μ_{2} ; μ_{1} δ) ≤ B(μ_{2}, δ).

Doob lényegesen általánosabb alakban mondta ki a következő egyenlőtlenségét, nekünk elég lesz a következő alak.

Tétel 15.4. (Doob) Legyen az (X_{n}, F_{n}) sorozat szubmartingál, X_{n}^{⋆} = max(X_{1}, X_{2}, …, X_{n}), λ > 0. Ekkor

λℙ (X_{n}^{⋆} > λ) < ∫_{{X_{n}^{⋆}>λ}} X_{n}dP.

A Doob egyenlőtlenség segítségével Hoeffding egyenlőtlensége a következőképpen erősíthető.

Tétel 15.5. Legyenek X_{1}, X_{2}, …, X_{n} független valószínűségi változók, a_{i} ≤ X_{i} ≤ b_{i},

t > 0, S_{k} = ∑_{i=1}^{k} X_{i}. Ekkor

ℙ ( max_{1≤k≤n}(S_{k} − 𝔼S_{k}) > t) < exp (− 2t^{2} ; ∑_{i=1}^{n}(b_{i} − a_{i})^{2} ) .

Proof. Az S_{k} − 𝔼S_{k} (k = 1, 2, …, n) sorozat martingál, és tetszőleges h > 0-ra az exponenciális függvény konvexitása és monotonitása miatt exp (hS_{k} − h𝔼S_{k}) (k = 1, 2, …, n) nemnegativ szubmartingál sorozat. A Doob egyenlőtéenség miatt

ℙ ( max_{1≤k≤n}(S_{k} − 𝔼S_{k}) > t) =

= ℙ ( max_{1≤k≤n} e^{h(S_{k}−𝔼S_{k})} > e^{ht}) < e^{−ht}𝔼e^{h(S_{n}−𝔼S_{n})}.

Innen pedig a bizonyítás az eredeti bizonyítással megegyezően befejezhető. Az javítást azzal értük el, hogy a Markov-egyenlőtlenség helyett a Doob-egyenlőtlenséget használtuk.

Referenciák

[Al] N. Alon, A parallel algorithmic version of the Local Lemma, Random Structures & Algorithms, 2 (1991), 367-378.

[AlSp] N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience Series, John Wiley & Sons, Inc., New York, 1992.

[Ban] W. Banaszczyk, The Steinitz constant of the plane, J. Reine Angew. Math. 373 (1987) 218-220; MR 88e:52016.

[Ba] I. Bárány, On a Class of Balancing Games Journal of Combinatorial Theory, Series A, Vol. 26, No. 2, March 1979.

[BaFi] Bárány Imre, Fiala Tibor, Többgépes ütemezési problémák közel optimális megoldása Szigma, 15 (3) (1982) 177-191.

[BaGr] I. Bárány and V. S. Grinberg, On Some Combinatorial Questions in Finite-Dimensional Spaces, Linear Algebra and Its Applications, 41 (1981), 1-9.

[Be] J. Beck, An Algorithmic Approach to the Lovász Local Lemma, Random Structures & Algorithms, 2 (1991), 343-365.

[BeFi] J. Beck, T. Fiala, “Integer-Making” Theorems, Discrete Applied Mathematics 3 (1981), 1-8.

[BeS] J. Beck and V. T. Sós, Discrepancy Theory, Handbook of Combinatorics, R. Graham, M. Grötsel and L. Lovász eds., Elsevier, 1995, 1405-1446.

[Lu] Chi-Jen Lu, A Determinsitic Approximation Algorithm for a Minmax Integer Programming Problem, Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, (1999), 663-668.

[DoSr] Benjamin Doerr, Anand Srivastav, Approximation of Multi-color Discrepancy

[Do] Benjamin Doerr, Multi-Color Discrepancies

[EL] P. Erdős and L. Lovász, Problems and Results on 3-chromatic Hypergraphs and Some Related Questions, Infinite and Finite Sets, A. Hajnal et al., eds., Colloq. Math. Soc. J. Bolyai 11, North Holland, Amsterdam, 1975, 609-627.

[GoSa] T. Gonzales, S. Sahni, Open shop scheduling to minimze finishing time, J. ACM 23 (1976) 665-679.

[GrSe] V. S. Grinberg, S. V. Sevastyanov, O velicine konstanty Steinica, Funkcionalnij Analiz i Prilozen., 14/2 (1980), 56-57 (in Russian); Engl. transl. in Functional Anal. Appl. 14 (1980) 125-126, MR 81h:52008.

[Hoc] D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, PWS Press, 1997.

[Hoe] W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, American Statistical Assoc. J., 58 (1963), 13-30.

[LRS] T. Leighton, S. Rao and A. Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, (1999), 643-652.

[LSV] L. Lovász, J. Spencer and K. Vesztergombi, Discrepancy of set-systems and matrices, European Journal of Combinatorics, 7 (1986), 151-160.

[MR] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[Ra] P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs, J. of Computer and System Sciences, 37 (1988), 130-143.

[RT] P. Raghavan and C. D. Thompson, Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs, Combinatorica, 7 (1987), 365-374.

[Se1] S. V Sevastyanov, On some geometric methods in scheduling theory: a survey, Discrete Applied Mathematics, 55 (1994), 59-82.

[Se2] S. V Sevastyanov, Seven problems: so different yet close,

[Sp1] J. Spencer, Balancing Games, J. Combinatorial Th., Ser B, 23 (1977), 68-74.

[Sp2] J. Spencer, Balancing Vectors in the Max Norm, Combinatorica, 6 (1986), 55-65.

[Sp3] J. Spencer, Randomization, derandomization and antirandomization: three games, Theoretical Computer Science, 131 (1994), 415-429.

[Sp4] J. Spencer, Six Standard Deviations Suffice, Trans. Amer. Math. Soc., 289 (1985), 679-706.

[Sr1] A. Srinivasan, An Extention of the Lovász Local Lemma, and its Applications to Integer Programming, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, (1996), 6-15.

[Sr2] A. Srinivasan, A Survey of the Role of Multicommodity Flow and Randomization in Network Design and Routing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 43 (1999).

[SzT] Szőnyi Tamás, Szimmetrikus struktúrák, Egyetemi jegyzet.