Improved algorithms via random sampling

通过随机采样改进算法

• 批准号: DP210103849
• 负责人: Prof Serge Gaspers
• 金额: $ 30.6万
• 依托单位: The University of New South Wales
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2021
• 资助国家: 澳大利亚
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP210103849
• 关键词: 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.

当涉及到解决计算上“棘手”的子集问题时，随机化方法最近进入了聚光灯下。通过将一系列算法的第一步替换为一种简单的方法，即向解中均匀地添加一个小子集，并多次重复该过程，一系列算法的运行时间得到了改善。这个项目将探索(不一定是均匀的)随机抽样如何改善算法的运行时间的各种其他方法；并探索多项式时间随机化算法的分析。该项目将专注于在操作系统、芯片设计和验证、设施定位以及监视和监测中应用的周期割集和支配问题。