论文标题
实验设计的本地搜索框架
A Local Search Framework for Experimental Design
论文作者
论文摘要
我们提出了一个本地搜索框架，以设计和分析组合算法和实验设计问题的圆形算法。该框架提供了一种统一的方法，可以在D/A/E-Design中匹配和改善所有已知结果，并在以前未知的设置中获得新的结果。 对于组合算法，我们对经典Fedorov的交换方法提供了新的分析。我们证明，只要存在一个几乎最佳的解决方案，这种简单的本地搜索算法就可以很好地工作。此外，我们使用遗憾最小化框架设计了一种新的组合本地搜索算法，用于电子设计。 对于四舍五入算法，我们提供了一种统一的随机交换算法，以匹配并改善D/A/E-Design的先前结果。此外，该算法在更通用的环境中起作用，可大致满足多个背包的约束，可用于加权实验设计，并将公平约束纳入实验设计。
We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for experimental design problems. This framework provides a unifying approach to match and improve all known results in D/A/E-design and to obtain new results in previously unknown settings. For combinatorial algorithms, we provide a new analysis of the classical Fedorov's exchange method. We prove that this simple local search algorithm works well as long as there exists an almost optimal solution with good condition number. Moreover, we design a new combinatorial local search algorithm for E-design using the regret minimization framework. For rounding algorithms, we provide a unified randomized exchange algorithm to match and improve previous results for D/A/E-design. Furthermore, the algorithm works in the more general setting to approximately satisfy multiple knapsack constraints, which can be used for weighted experimental design and for incorporating fairness constraints into experimental design.
