|
|
Parameterized Approximations of Directed Steiner Networks
Koreček, Martin ; Feldmann, Andreas Emil (vedoucí práce) ; Marx, Dániel (oponent)
Instance problému orientované Steinerovy sítě (zkracováno na DSN podle anglického názvu) je tvořena orientovaným grafem G s cenami hran a k tzv. "terminálními" páry vrcholů. Cílem je najít podgraf G s minimální cenou, ve kterém je každý terminální pár propojen cestou. Toto zobecňuje několik NP-těžkých problémů. Terminální páry indukují takzvaný "vzorový graf", orientovaný graf na podmnožině vrcholů G. V této práci se zabýváme problémem DSN omezeným na určité třídy vzorových grafů. Ví se, že optimum lze najít v FPT čase pro některé třídy, a že to není možné pro všechny ostatní třídy, za předpokladu že FPT ̸= W[1]. To vede na otázku, jak dobře lze ony těžké třídy aproximovat v FPT čase. Doká- žeme, že pro ně neexistuje FPT aproximační schéma na základě silnějšího předpokladu, Gap-ETH hypotézy. Poté ukážeme algoritmy s konstantním aproximačním faktorem pro speciální třídy vzorových grafů. 1
|
|
|
A Comparison of Strategies for Database Caching
Koreček, Martin ; Brown, Williams (vedoucí práce) ; Kofroň, Jan (oponent)
Database caching is the practice of keeping an amount of data in memory, to reduce the cost of accesses to the main storage, and thus improve the performance of a database machine. We particularly focus on two properties of database caches. Firstly, how differ- ent cache replacement policies decide what data is kept in memory and secondly, what options exist to allow parallel accesses to the cached set by multiple threads. With a lim- ited resource of access logs from real NoSQL databases in production, we will measure the performance of the discussed replacement policies. And we will measure the in-memory performance of the data structures that enable parallelism. 1
|
host ::
RSS.