|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (advisor) ; Fellows, Michael R. (referee) ; Tantau, Till (referee)
In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity
|
|
|
Flows Along Paths of Bounded Length
Altmanová, Kateřina ; Kolman, Petr (advisor) ; Pangrác, Ondřej (referee)
In this bachelors's thesis we study the problem of k-bounded flows, i.e. flows which can be decomposed to flow paths of lenght bounded by a constant k. We review some known results in this field of study and we mention also the problem of k-bounded cut, which is a subset of edges from the flow network s. t. the flow ne- twork without these edges does not have any k-bounded flow. The main aim of this thesis is a detailed explaration of the article The Maximum k-flow in a Network written by V. Koubek a A. Říha, published as a conference paper in Mathematical Foundations of Coputer Science 1981, pages 389-397, providing an explanation of compticated passages and completition of some of the main proofs which are ommited in the paper mentioned above. The aim of completing proofs is not accomplished due to finding a serious mistake in the conference paper. Instead of completing proofs we provide a description why the algorithm in the paper does not work. 1
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (advisor) ; Kolman, Petr (referee)
Abstract. The thesis is devoted to the problem of online preemptive scheduling of mul- tiprocessor jobs. It gives a summary of previous work on this problem. For some special variants of the problem, especially if we restrict the sizes of jobs to one and two, new results are given, both in the terms of lower bounds and in the terms of competitive al- gorithms. A previously published lower bound is showed to be computed incorrectly and it is replaced by a correct lower bound in this thesis. An algorithm is presented for the special case of four processors and sizes of jobs one and two that is conjectured to achieve the best possible competitive ratio.
|
|
|
ACTOR AS A CREATOR OF SOUND COMPONENT IN A AUTHOR`S PROJECT
Kolman, Petr ; ČTVRTNÍK, Jan (advisor) ; ŠRÁMEK, Vratislav (referee)
The bachelor thesis contains a brief insight into the theory of music and sound on
the stage. Describes differences in the use of sound between specific types of
theater. It continues with the personal reflection of the author of the work and
describes his most crucial moments during his studies, when he met with the music
as an actor on stage, how he worked and how he benefited from it.
|
|
|
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...
|
|
|
Algoritmy pro L-omezené toky
Voborník, Jan ; Kolman, Petr (advisor) ; Kučera, Luděk (referee)
We study the problem of maximum $L$-bounded flow, a flow decomposable to flow paths of length bounded by $L$. We review the basic results and related problems. Maximum $L$-bounded flow can be computed in polynomial time in networks with unit edge lengths but combinatorial algorithm is not known. We study combinatorial approach to this question. In networks with general edge lengths, the problem is \cNP-hard; for this problem we describe a fully polynomial approximation scheme (FPTAS) based on an algorithm for maximum multicommodity flow. This approach is practically more efficient than the previous FPTAS which was based on the ellipsoid method. Powered by TCPDF (www.tcpdf.org)
|
|
|
Obtížné problémy vzhledem k parametru různorodost sousedství
Koutecký, Martin ; Kolman, Petr (advisor) ; Fiala, Jiří (referee)
Parameterized complexity is a part of computer science dealing with the computational complexity of problems measured not only by the length of their input but also some parameter of the input. Nei- ghborhood diversity is a recently introduced parameter describing a certain structure of a graph. is parameter is aractive for resear especially because some problems whi are hard with respect to other parameters that are incomparable with neighborhood diversity become fixed-parameter tractable with respect to neighborhood diversity. In this thesis we show fixed-parameter tractability for three problems that are hard with respect to treewidth. is constitutes the main part of this thesis and it is our original work. Next it contains an overview of other interesting problems and also a survey of the state of the art in the area of parameters for sparse and dense graphs. 1
|
|
|
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (advisor) ; Tiwary, Hans Raj (referee)
Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Flows and cuts with restriction
Knop, Dušan ; Kolman, Petr (advisor) ; Krčál, Marek (referee)
Title: Flows and cuts with constraints Author: Dušan Knop Department: Department of applied mathematics Supervisor: Doc. Mgr. Petr Kolman, PhD, Department of applied mathematics Abstract: In this thesis we study the problem of length bounded cuts between two vertices of a graph. In this problem the task is to find a set of edges such that after its removal the minimal distance between the two vertices is as prescribed. The work provides a basic overview of the literature on this problem and presents it in the context of other theoretical problems. It also offers some applications of length bounded cuts and flows. We describe some heuristics for data reduction. The main result of this thesis is a polynomial time algorithm in series-parallel graphs for problem of length bounded cut, which is NP-hard in general. Keywords: cuts, series-parallel graphs, algorithm, complexity
|
|
|
Optimization in graphs with bounded treewidth
Koutecký, Martin ; Kolman, Petr (advisor) ; Kráľ, Daniel (referee)
Courcelle's theorem speaks about computational complexity of decision problems defined by formulae in monadic second order logic over relational structures with bounded treewodth. For a fixed treewidth and a fixed formula, Courcelle's theorem gives an algorithm, which decides the formula over a structure of said treewidth in linear time. is thesis provides a self-contained proof of Courcelle's theorem using methods of finite model theory. Furthermore it contains the proofs of all propositions and theorems upon which the main proof depends, notably the Ehrenfeucht-Fraïssé theorem widely used in finite model theory. e thesis also contains an implementa- tion of an algorithm which follows from the main proof. Finally a sketch of the current state of the art of the area of research is given, as well as the possibilities following from it. 1
|
guest ::
RSS feed.