Analysis of Randomized Algorithms: Markov Chain Approach

点击翻译按钮获取中文摘要

The objective of this research is to establish methods for theoretical study in an important area of theoretical computer science, which isthe analysis of randomized algorithms. The main focus is on problemsthat either can be modeled by Markov chains or can be analyzed usingthe Markov chain approach.This project concentrates on three main topics: (1) general analysisof discrete-time Markov chains and the Monte Carlo Markov Chainmethod, (2) analysis of Markov chains for generating randompermutations, and (3) resource allocation problems in distributedsystems.In the area of general analysis of Markov chains the goal of theresearch is to develop new tools for the analysis of mixing times ofMarkov chains. An important part of this study is to investigaterelationships between various known methods of the analysis of mixingtimes of Markov chains.In the investigations of Markov chains for generating randompermutations the main focus is on so called random switchingnetworks. These networks model behavior of many Markov chains thatare sought in applications in cryptography.In the area of resource allocation problems in distributed systems,the research focuses mostly on resource allocation problems innetworks, in which the cost of the allocation depend on the routingproperties of the input network as well as on the contentionresolution protocols applied to the system.