|
|
Graph communication protocols
Folwarczný, Lukáš ; Pudlák, Pavel (advisor) ; Sgall, Jiří (referee)
Graph communication protocols are a generalization of classical communi- cation protocols to the case when the underlying graph is a directed acyclic graph. Motivated by potential applications in proof complexity, we study variants of graph communication protocols and relations between them. The main result is a comparison of the strength of two types of protocols, protocols with equality and protocols with a conjunction of a constant num- ber of inequalities. We prove that protocols of the first type are at least as strong as protocols of the second type in the following sense: For a Boolean function f, if there is a protocol with a conjunction of a constant number of inequalities of polynomial size solving f, then there is a protocol with equality of polynomial size solving f. We also introduce two new types of graph communication protocols, protocols with disjointness and protocols with non-disjointness, and prove that the first type is at least as strong as the previously considered protocols and that the second type is too strong to be useful for applications.
|
|
|
Approximation and Online Algorithms
Tichý, Tomáš ; Sgall, Jiří (advisor) ; Kolman, Petr (referee) ; van Stee, Rob (referee)
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...
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
|
|
Online algorithms for variants of bin packing
Veselý, Pavel ; Sgall, Jiří (advisor) ; Krčál, Marek (referee)
An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, a standard worst-case analysis, and present main results of this analysis on the problem of online Bin Packing and on some of its variants. In Bin Packing, a sequence of items of size up to 1 arrives to be packed into the minimal number of unit capacity bins. Mainly, we focus on Colored Bin Packing in which items have also a color and we cannot pack two items of the same color adjacently in a bin. For Colored Bin Packing, we improve some previous results on the problem with two colors and present the first results for arbitrarily many colors. Most notably, in the important case when all items have size zero, we give an optimal 1.5-competitive algorithm. For items of arbitrary size we present a lower bound of 2.5 and a 3.5-competitive algorithm. Powered by TCPDF (www.tcpdf.org)
|
|
|
Combinatorial Games Theory
Valla, Tomáš ; Nešetřil, Jaroslav (advisor) ; Sgall, Jiří (referee) ; Spirakis, Paul (referee)
Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...
|
|
|
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
Ebenlendr, Tomáš ; Sgall, Jiří (advisor) ; Barták, Roman (referee) ; Epstein, Leah (referee) ; Woeginger, Gerhard (referee)
Mgr. Tomáš Ebenlendr Combinatorial algorithms for online problems: Semi-online scheduling on related machines Abstract of doctoral thesis We construct a framework that gives optimal algorithms for a whole class of scheduling problems. This class covers the most studied semi-online variants of preemptive online scheduling on uniformly related machines with the objective to minimize makespan. The algorithms from our framework are deterministic, yet they are optimal even among all randomized algorithms. In addition, they are optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. We provide new lower bound of 2.112 for the original online problem. The (deterministic) upper bound is e ≈ 2.718 as there was known e-competitive randomized algorithm before. Our framework applies to all semi-online variants which are based on some knowledge about the input sequence. I.e., they are restrictions of the set of valid inputs. We use our framework to study restrictions that were studied before, and we derive some new bounds. Namely we study known sum of processing times, known maximal processing time, sorted (decreasing) jobs, tightly grouped processing times, approximately known optimal makespan and few combinations. Based on the analysis...
|
|
|
Interval Representations of Boolean Functions
Kronus, David ; Čepek, Ondřej (advisor) ; Sgall, Jiří (referee) ; Savický, Petr (referee)
This thesis is dedicated to a research concerning representations of Boolean functions. We present the concept of a representation using intervals of integers. Boolean function f is represented by set I of intervals, if it is true just on those input vectors, which correspond to integers belonging to intervals in I, where the correspondence between vectors and integers depends on the ordering of bits determining their significancies. We define the classes of k-interval functions, which can be represented by at most k intervals with respect to a suitable ordering of variables, and we provide a full description of inclusion relations among the classes of threshold, 2-monotonic and k-interval Boolean functions (for various values of k). The possibility to recognize in polynomial time, whether a given function belongs to a specified class of Boolean functions, is another fundamental and practically important property of any class of functions. Our results concerning interval functions recognition include a proof of co-NP- hardness of the general problem and polynomial-time algorithms for several restricted variants, such as recognition of 1-interval and 2-interval positive functions. We also present an algorithm recognizing general 1-interval functions provided that their DNF representation satisfies several...
|
|
| |
|
|
Algorithms for scheduling with conflicts
Zajíček, Ondřej ; Sgall, Jiří (advisor) ; Čepek, Ondřej (referee)
Scheduling with conflicts supposes graph of conflicts. Vertices of that graph represent machines and edges represent conflicts between them. Every machine can be switched on or switched off . Two conflicting machines cannot be both switched on at the same time. At certain times new tasks arrive to speci c machines and enqueue to its input buff ers. Each machine continuously processes tasks from its input bu ffer whenever it is switched on. An algorithm decides which machines should be switched on or switched o ff at any time, obeying conflict constraints. The objective is to schedule machine switching to minimize the maximum bu er size of all processors. The problem is online, so an algorithm has to make decisions about current con ffiguration without knowledge of future tasks. In this thesis I consider the algorithm based on maximization of scalar product of work vector (vector describing con guration of machines) and vector of bu ffer lengths. I prove that this algorithm is well de ffined, finite on every input and for speciffi c graph (path of length 3) it has competitive ratio of 7=3. Further I consider possibilities of implementation of that algorithm.
|
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (advisor) ; Sgall, Jiří (referee)
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this thesis, we study the computational complexity the problem S(P) for a certain graph property P: given a graph G, determine if G is switching-equivalent to a graph having P. First, we give an overview of known results, including both properties P for which S(P) is polynomial, and those for which S(P) is NP-complete. Then we show the NP-completeness of the following problem for each c (0; 1): determine if a graph G can be switched to contain a clique of size at least cn, where n is the number of vertices of G. We also study the problem if, for a xed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial. Further, we give a characterization of graphs witching-equivalent to a K1;2-free graph by ten forbidden induced subgraphs, each having ve vertices.
|
guest ::
