论文标题
对称性：从证明到算法，然后返回
Symmetries: From Proofs To Algorithms And Back
论文作者
论文摘要
如果在任何算法中交换了两个部分后，我们将目的函数或算法对称为对称，则该算法的解决方案和输出保持不变。更正式的是，对于索引输入的排列$π$，以及另一个相同输入的排列$π'$，以便将两个项目转换为$π$，$π$，$ f（π）= f（π）= f（π'）$，其中$ f $是目标函数。 在回顾了利用对称性的算法的样本后，我们提供了几个新的，用于查找较低限制，在线算法中击败对手，设计并行算法和数据汇总。我们展示了如何使用采样点之间的对称性来获得溶液上的下部/上限。这主要取决于交换时输入部分的等效类别，请勿更改解决方案或成本。
We call an objective function or algorithm symmetric with respect to an input if after swapping two parts of the input in any algorithm, the solution of the algorithm and the output remain the same. More formally, for a permutation $π$ of an indexed input, and another permutation $π'$ of the same input, such that swapping two items converts $π$ to $π'$, $f(π)=f(π')$, where $f$ is the objective function. After reviewing samples of the algorithms that exploit symmetry, we give several new ones, for finding lower-bounds, beating adversaries in online algorithms, designing parallel algorithms and data summarization. We show how to use the symmetry between the sampled points to get a lower/upper bound on the solution. This mostly depends on the equivalence class of the parts of the input that when swapped, do not change the solution or its cost.
