|
|
Heuristics for Length Bounded Cuts
Madaj, Pavel ; Kolman, Petr (advisor) ; Koutecký, Martin (referee)
This thesis deals with the problem of finding a minimum length-bounded cut in a graph. We first provide a brief overview of the problem and its applications. We then discuss the known theoretical results and approximation algorithms. We look at the existing linear programming formulations and propose a new one. A concise discussion on potential hard instances, utilized for testing our formulations, is also incorporated. The focus of our analysis is on the performance and behavior of our proposed linear programming family, contrasting it with the established natural formulation. We also compare the performance of various heuristics and approximation algorithms in practice by examining their behaviour on a large set of small instances. 1
|
|
|
Efficient representation of k-mer sets
Milyutina, Ekaterina ; Veselý, Pavel (advisor) ; Kolman, Petr (referee)
In this thesis we explore and compare various methods for efficient k-mer set representation. We evaluate traditional de Bruijn graph representation techniques against greedy approximation algorithms for the Shortest Superstring Problem. We describe the linear- time implementation of the well-known Greedy algorithm by Ukkonen [1990] and extend it to another related algorithm, called TGreedy. In addition, we test selected algorithms on a bacterial genome and pangenome to highlight the differences in the size of their output representation and the computational resources used, providing an insight into their respective efficiencies.
|
|
|
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...
|
|
|
Clustering techniques for ads monitoring
Dzetkulič, Tomáš ; Kolman, Petr (advisor) ; Kára, Jan (referee)
This thesis surveys possibilities of clustering of advertisements, especially those for real estates. It defines clustering itself, its usage and typical requirements for clustering algorithms. We provide list of existing clustering methods and approaches, their properties and suitable application. We consider possiblity of using them for clustering of milions of advertisements and based on that, we choose most suitable algorithm for this problem. We describe how to interpret advertisement as the point in multi dimensional vector space and this algorithm for clustering such points using locality of families of hash functions. We describe algorithm in detail, listing all of its parameters, estimating its complexity and expected results. In the following chapters we describe implementation of the algorithm in Java. We also describe database structure of underlying relational database. In the next chapter we present results of the algorithm based on real data and we compare the results with the expected results of the algorithm. In the end, we discuss possibilities for future extension of the clustering method.
|
|
|
The optimal route search under several criteria
Vodička, Jan ; Fiala, Jiří (advisor) ; Kolman, Petr (referee)
Common methods of optimal route search are described in the thesis. Also, existing procedures used in problematics of transportation networks are mentioned. A nonlinear price function is proposed, which enables the user to specify their own preferences of any criteria (length, time, cost, etc.). Moreover, necessary modifications of common optimal route searching algorithms are presented. A method for propagation of maneouvres of arbitrary length into the transportation network is shown. This method enlarges nodes and vertices sets by amount linearly proportional to number of nodes involved in maneouvre set. Also, a general method diminishing the number of edges, which have to be encountered during optimal raute search process, is proposed. Precalculated edges sets are used to gain this goal. Proposed thesis contains three methods solving specific aspects of optimal route search in transportation networks. While the first method, when applied in practice, can bring limitations of processable data size, the other two procedures forrn the basis of a navigation system. Powered by TCPDF (www.tcpdf.org)
|
|
|
Half-automatic recognition of text structure
Šenkýř, Michal ; Kolman, Petr (advisor) ; Skopal, Tomáš (referee)
This thesis describes the design and implementation of an algorithm that, using some initial hints from the user, converts data in HTML documents generated from a database and inteded for human readability, into a structured form suitable for computer processing. The input document is assumed to have some structure (usually a visual layout) and the user must provide a sample of semantically labelled items in the document. The output is expected to reflect the semantic structure of the provided data. The resulting application is composed of an editor part which includes a graphical tool for easy labelling of sample items, and a server part, which includes a tool for the subsequent mass processing of additional documents. The application was tested on real estate advertising webs and the results of the testing were analysed. The thesis also surveys other existing applications based on similar principles and provides their comparison.
|
|
|
Shortest paths when searching for travel connections
Hronik, Jan ; Kolman, Petr (advisor) ; Škovroň, Petr (referee)
We deal with algorithms for finding cheapest connections in a transportation network with timetables where a cheapest connection is one with the lowest value given some evaluation function. A problem of cheapest connection in a transportation network is introduced and formalized, and is reduced to a shortest path problem in a directed graph. A representation of a transportation network by a directed graph is thereafter given, and several standard algorithms for the shortest path problem are described in turn. Several optimizations of the algorithms for their application to the transportation network are proposed. Eventually, performance results of the algorithms are presented along with their comparison. The algorithms were tested on (1) the train network of the Czech Republic, and on (2) a randomly generated graph.
|
|
|
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)
|
|
|
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
|
|
|
Length bounded cuts in graphs
Berg, Michal ; Kolman, Petr (advisor) ; Dvořák, Pavel (referee)
In this thesis we will focus on a problem of length bounded cut, also known as L-bounded cut. We are going to show a combinatorial algorithm for finding a minimal L-bounded cut on graphs with bounded treewidth based on dynamic programming. Then we going to show that this algorithm can also be used for finding minimal L-bounded cut on plannar graphs. We are also going to look at problem of (dG(s, t) + 1)-bounded cut. This problem is known to be NP-hard for general graphs. But it is an open problem whether this problem is also NP-hard on plannar graphs with special vertices on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.
|
guest ::
