National Repository of Grey Literature 2 records found  Search took 0.01 seconds. 
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)
Non-negative linear operators and their use in econometric and statistic models
Horský, Richard ; Arlt, Josef (advisor) ; Vrabec, Michal (referee) ; Klazar, Martin (referee)
Non-negative operators, in special case non-negative matrices, are an interesting topics for many scientists and scientific teams from the beginning of the 20th century. It is not suprising because there are a lot of applications in different areas of science like economy, statistics, linear programming, computer science and others. We can give as the particular example the theory of the Markov chains in which we deal with non-negative matrices, so called transition matrices. They are of the special form and we called them stochastic matrices. Another example is given by the non-negative operator on spaces of infinite dimension which is employed in the theory of stochastic processes. It is the backward shift operator called the lag operator as well. The non-negativity in these examples is considered as the piecewise non-negativity. Another type of non-negativity is that in the sense of inner products. In the case of matrices we talk about positive-definite or positive-semidefinite matrices. A typical example is the covariance matrix of a random vector or symmetrization of any linear operator, for instance the symmetrization of the difference operator. The terms inverse problem or ill-posed problem have been gaining popularity in modern science since the middle of the last century. The subjects of the first publications in this area were related to quantum scattering theory, geophysics, astronomy and others. Thanks to powerful computers the chances for applications of the theory of inverse and ill-posed problems has extended in almost all fields of science which use mathematical methods. Ill-posed problems bear the feature of instability and there is the need of regularization if we want to get some reasonable solution. A typical example of the regularization is the differencing of stochastic process with the purpose to obtain a stationary process. Another concept of regularization used for solving e.g. integral equations with compact operators consists in application of regularization method as truncated singular value decomposition, Tichonov regularization method or Landweber iteration method. Mathematical tools employed in this work are those of the functional analysis. It is the area of mathematics in which distinct mathematical structures meet each other. They are structures built within different mathematical disciplines as mathematical analysis, topology, theory of sets, algebra (mainly linear algebra) and theory of measure (probability). The functional analysis framework enables us to obtain right formulations of definitions and problems providing the general view on the notions and problems of the theory of stochastic processes.

Interested in being notified about new results for this query?
Subscribe to the RSS feed.