Analysis of Randomized Algorithms: Markov Chain Approach

这项研究的目的是在理论计算机科学的一个重要领域建立理论研究的方法，这就是随机算法的分析。本课题主要集中在可以用马尔可夫链建模或可以用马尔可夫链方法分析的问题上。本项目主要集中在三个主要主题上：(1)离散时间马尔可夫链的一般分析和蒙特卡洛马尔可夫链方法，(2)马尔可夫链随机排列的分析，以及(3)分布式系统中的资源分配问题。在马尔可夫链的一般分析领域，研究的目标是开发新的工具来分析马尔可夫链的混合时间。这项研究的一个重要部分是研究各种已知的马尔可夫链混合时间分析方法之间的关系。在产生随机排列的马氏链的研究中，主要集中在所谓的随机交换网络上。在分布式系统中的资源分配问题中，研究主要集中在网络中的资源分配问题上，其中分配的代价取决于输入网络的路由属性以及应用于系统的争议解决协议。

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.