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.
翻译:我们提出了一个本地搜索框架,用于设计和分析用于实验设计问题的组合算法和四舍五入算法。这个框架提供了一种统一的方法,以匹配和改进D/A/E-设计中所有已知结果,并在先前未知的环境下获得新结果。对于组合算法,我们提供了对古典Fedorov的交换方法的新分析。我们证明,只要存在一个具有良好条件编号的近乎最佳的解决方案,这种简单的本地搜索算法是有效的。此外,我们设计了一种新的组合本地搜索算法,用于使用最小度最小化框架进行电子设计。对于四舍五入算法,我们提供了一种统一的随机交换算法,以匹配和改进D/A/E-设计先前的结果。此外,在更笼统的环境下,算法可以大致满足多种 knapsack 限制,这些限制可用于加权实验设计,并将公平性限制纳入实验设计。