|
|
Two-phase scheduling with unknown speeds
Minařík, Josef ; Sgall, Jiří (vedoucí práce) ; Eberle, Franziska (oponent)
Rychlostně robustní rozvrhování je dvoufázový rozvrhovací problém. Na vstupu je dána doba běhu pro každý z n úkolů, počet strojů m a počet balíčků b. Naším úkolem je rozdělit úkoly do balíčků, které budou následně zpracovány na strojích, které mají v tomto okamžiku neznámé rychlosti. Naším cílem je minimalizovat poměr délky našeho rozvrhu a délky optimáního rozvrhu, který by vznil umisťováním úkolů rovnou na stroje. Nejpodrobněji studovaný případ doposud byl b = m. V této práci zobecňujeme známé výsledky pro infinitizemálně malé úkoly (tento případ se nazývá písek) a dokážeme, že nejlepší kompetitivní poměr, kterého je možné dosáhnout, je mb mb−(m−1)b . Dále formulujeme algoritmus řešící případ s identickými úkoly (nazývaný cihly) za podmínky b = m s kompetitivním poměrem 1.6, což zlepšuje nejlepší doposud známou hodnotu 1.8. Zavedeme nový speciální případ, který budeme nazývat p-oblázky. V tomto případě jsou doby běhu jednotlivých úkolů nejvýše p-násobky průměrné zátěže stroje. Oblázky jsou vlastnostmi i obtížností na půl cesty mezi pískem a obecným případem (nazývaným kameny). Popíšeme algoritmus pro oblázky, který je pro malé hodnoty p lepší než nejlepší známý algoritmus pro kameny (pro p menší než 2 − e e−1 v případě b = m). 1
|
|
|
Algorithms for timetabling in sports
Koštejn, Vít ; Sgall, Jiří (vedoucí práce) ; Vu, Tung Anh (oponent)
Tato bakalářská práce se zabývá problémem tvorby startovních listin pro orientační běh. Zaměřujeme se jak na teoretické tak na praktické výsledky. V teoretické části je problém převeden do terminologie rozvrhování a následně analyzován společně s jeho speciálními případy. Zajímáme se především o aproximační algoritmy a jejich poměry. V praktické části se zabýváme metodami pro generování startovních listin založených na dříve analyzovaných aproximačních algoritmech a na programování s omezujícími pod- mínkami. Následně jsou metody testovány na reálných datech z předchozích závodů a porovnávány s použitými startovními listinami. 1
|
|
|
Approximation and Online Algorithms
Tichý, Tomáš ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent) ; van Stee, Rob (oponent)
This thesis presents results of our research in the area of optimization problems with incomplete information-our research is focused on the online scheduling problems. Our research is based on the worst-case analysis of studied problems and algorithms; thus we use methods of the competitive analysis during our research. Althrough there are many "real-world" industrial and theoretical applications of the online scheduling problems there are still so many open problems with so simple description. Therefore it is important, interesting and also challenging to study the online scheduling problems and their simplified variants as well. In this thesis we have shown the following our results of our research on the online scheduling problems: A 1.58-competitive online algorithm for the problem of randomized scheduling of unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs ismaximized. A lower bound 1.172 on the competitive ratio for the problem of randomized scheduling of 2-uniform unit jobs on a single processor, where the jobs are arriving over time andthe totalweight of processed jobs is maximized. A lower bound 1.25 on the competitive ratio for the problem of randomized scheduling of s-uniform unit jobs on a single processor where s is tending to...
|
|
|
Algoritmy pro rozvrhování s konflikty
Zajíček, Ondřej ; Sgall, Jiří (vedoucí práce) ; Čepek, Ondřej (oponent)
Problém rozvrhování s konflikty předpokládá graf konfliktů, jehož vrcholy reprezentují stroje a hrany reprezentují konflikty mezi nimi. Každý stroj může být vypnutý nebo zapnutý. Stroje, které jsou v konfliktu, nemohou být zároveŇ zapnuté. Na jednotlivé stroje čas od času přicházejí úlohy a řadí se do vstupních front jednotlivých strojů. Zapnuté stroje průběžně úlohy zpracovávají a vyprazdňují tak své fronty. Algoritmus rozhoduje o vypínání a zapínání jednotlivých strojů, přičemž musí dodržet omezení vyplývající z grafu konfliktů. Cílem je najít takový rozvrh, který minimalizuje maximální dosaženou délku vstupních front. Problém je online, algoritmus tedy musí reagovat průběžně, přičemž neví, jaké úlohy se objeví později. Navrhl jsem algoritmus založený na maximalizaci skalárního součinu pracovního vektoru (vektoru, reprezentujícího konfiguraci jednotlivých strojů) a vektoru délek front. V této práci dokazuji, že tento algoritmus je dobře de finován, je vždy konečný a pro konkrétní graf (cestu délky 3) je jeho kompetitivní poměr 7=3. Dále v práci rozebírám možnosti implementace tohoto algoritmu.
|
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Sgall, Jiří (oponent)
Seidelovo přepnutí je grafová operace, která změní hrany vycházející z daného vrcholu tak, aby sousedil s právě těmi vrcholy, které původně nebyly jeho sousedy; zbytek grafu zůstane nezměněn. Dva grafy nazveme ekvivalentní v přepnutí, pokud lze pomocí posloupnosti přepnutí jeden z nich převést na izomorfní tomu druhému. V této práci studujeme výpočetní složitost problému S(P) pro určitou grafovou vlastnost P: je daný graf G ekvivalentní v přepnutí nějakému grafu, který má vlastnost P? Neprve podáváme přehled známých výsledků, vlastností P, pro které je problém S(P) polynomiální, i těch, pro které je NP-úplný. Poté ukážeme NP-úplnost následujícího problému pro každé c (0; 1): lze daný graf G přepnout tak, aby obsahoval kliku velikosti alespoň cn, kde n je počet vrcholů grafu G? Zabýváme se také problémem pro pevně zvolený graf H rozhodnout, zda je daný graf G ekvivalentní v přepnutí nějakému H-prostému grafu. Ukážeme, že je-li H izomorfní spáru, tento problém je polynomiální. Dále podáváme charakterizaci grafů, které jsou ekvivalentní v přepnutí nějakému K1;2-prostému grafu, pomocí deseti zakázaných indukovaných podgrafů, z nichž každý má pět vrcholů.
|
|
|
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
Ebenlendr, Tomáš ; Sgall, Jiří (vedoucí práce) ; Barták, Roman (oponent) ; Epstein, Leah (oponent) ; Woeginger, Gerhard (oponent)
Mgr. Tomáš Ebenlendr Kombinatorické algoritmy se zaměřením na online problémy: Semi-online rozvrhování na strojích s různými rychlostmi Abstrakt disertační práce Hlavním výsledkem této práce je konstrukce optimálních algoritmů pro celou třídu rozvrhovacích problémů. Tato třída zahrnuje většinu zkoumaných semi-online vari- ant preemptivního rozvrhování na strojích s různými rychlostmi s cílem minimali- zovat délku rozvrhu. Takto zkonstruované algoritmy jsou deterministické, nicméně dosahují optimální kompetitivní poměr i mezi pravděpodobnostními algoritmy. Navíc jsou optimální i pro libovolnou pevnou kombinaci rychlostí strojů, proto lze naši konstrukci uplatnit i na veškeré dříve studované speciální případy. Ukážeme nový dolní odhad 2.112 pro obecné online rozvrhování. Deterministický horní odhad e ≈ 2.718 pak plyne z dřívější existence e-kompetitivního pravděpodob- nostního algoritmu. Zmíněnou konstrukci lze aplikovat ve všech semi-online variantách, které jsou založeny na znalosti o vstupní sekvenci. Ty lze chápat jako omezení množiny plat- ných vstupů. Tuto konstrukci pak použijeme ke studiu dříve zkoumaných omezení, čímž získáme nové odhady kompetitivního poměru. Jmenovitě zkoumáme známou sumu...
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
|
|
Online Algorithms for Packet Scheduling
Veselý, Pavel ; Sgall, Jiří (vedoucí práce) ; Stein, Clifford (oponent) ; Englert, Matthias (oponent)
V této práci studujeme rozvrhovací algoritmy pro abstraktní modely sít'ového přepínače, v nichž přicházejí pakety do bufferu přepínače, aby byly odeslány skrz výstupní port. Počet paketů přicházejících do bufferu je však příliš veliký a některé tak nemohou být odeslány. Pakety mají prioritu danou váhou a cílem algoritmu je maximalizovat propustnost systému, tedy celko- vou váhu odeslaných paketů. Algoritmus nicméně nezná pakety, které přijdou v budoucnu, a nedosáhne tedy optimální propustnosti. Proto provádíme kom- petitivní analýzu a její zjemnění, jež analyzují chování online algoritmů v nejhorších případech. V první části práce se zaměříme na jednoduchý online rozvrhovací model s pakety jednotkové délky s termíny, zvaný Bounded-Delay Packet Scheduling. Navrhneme optimální φ-kompetitivní deterministický algoritmus pro tento problém, kde φ ≈ 1.618 je zlatý řez. Algoritmus je založen na detailním roz- boru struktury optimálních rozvrhů paketů v bufferu, zvaných plány. Dále se zaměříme na semi-online algoritmy s tzv. lookaheadem, který umožňuje algoritmu vidět pakety přicházející v nejbližší budoucnosti. Ukážeme algorit- mus s lookaheadem pro instance, v nichž každý paket může být rozvrhnut pouze...
|
|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (vedoucí práce) ; Durr, Christoph (oponent) ; Kellerer, Hans (oponent)
Online Bin Stretching: algoritmy a strojové dolní odhady Autor: Martin Böhm Abstrakt: Zabýváme se problémem v oblasti semi-online algoritmů, který se nazývá Online Bin Stretching. Můžeme tento problém chápat jako pro- blém opětovného pakování předmětů: cílem algoritmu je zapakovat před- měty různých velikostí do m kontejnerů identické kapacity R > 1. Objekty na vstupu přicházejí jeden po druhém a algoritmus musí přiřadit předmět do kontejneru dříve, než se objeví předmět další. Zvláštnost tohoto konkrétního problému je existence zaručené vlastnosti vstupu, kterou algoritmus zná. Algoritmus totiž už od začátku vstupu má zaručeno, že existuje pakování celého vstupu do m kontejnerů kapacity 1. Naším cílem je navrhnout algoritmy, které pakují jeden objekt po dru- hém a kterým se podaří vstup zapakovat do co nejmenší možné kapacity R. V této dizertační práci představíme několik nových výsledků kolem On- line Bin Stretchingu. Zaprvé, navrhneme algoritmus, který napakuje všechny objekty do m kontejnerů s kapacitou 1,5, a to pro libovolnou počáteční hodnotu m. Zadruhé se soustředíme na podproblém, ve kterém je počet kontejnerů nízký a pevný, například 3. Pro tento model představíme algo- ritmus, který zapakuje vstup do 3 binů s kapacitou 1,375. Nakonec navrhneme a naimplementujeme počítačový program, který bude...
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent)
Abstrakt. Práce se věnuje problému preemptivního online rozvrhování paralelních úloh. Podává přehled předchozích výsledků pro tento problém. Pro některé speciální varianty problému, například pro úlohy na jeden a dva procesory, poskytuje nové výsledky, jak v podobě dolních odhadů, tak v podobě kompetitivních algoritmů. Je objevena chyba v dříve publikovaném dolním odhadu a opravena na správný dolní odhad. Je navržen algoritmus pro verzi problému se čtyřmi procesory a s úlohami na jeden a dva procesory, pro který je vyslovena hypotéza, že dosahuje nejlepšího možného kompetitivního poměru.
|
host ::
RSS.