Improved algorithms via random sampling

随机方法最近成为人们关注的焦点，当涉及到解决计算“棘手”的子集问题。一系列算法的运行时间已经得到改善，通过将它们的第一步替换为一种简单的方法，即随机均匀地向解决方案添加一个小子集，并重复该过程多次。这个项目将探索各种其他方式（不一定是均匀的）随机抽样如何提高算法的运行时间;并探索多项式时间随机算法的分析。该项目将重点研究在操作系统、芯片设计和验证、设施定位以及监视和监测中有应用的周期割集和支配问题。

Randomized methods have recently come into the spotlight when it comes to solving computationally "intractable" subset problems. The running time of a range of algorithms has been improved by replacing their first steps by a simple method of adding to the solution a small subset uniformly at random, and repeating the process many times. This project will explore various other ways how (not necessarily uniform) random sampling can improve the running time of algorithms; and explore the analysis of polynomial-time randomized algorithms. The project will focus on cycle cutsets and domination problems that have applications in operating systems, chip design and verification, facility location, and surveillance and monitoring.