论文标题
较低的密度选择方案通过小型通用击球集，剩余路径长度短
Lower density selection schemes via small universal hitting sets with short remaining path length
论文作者
论文摘要
通用击球集是不可避免的单词集：每一个足够长的顺序都被集合击中（即，它包含了集合中的单词）。通用击球集与最小化方案之间存在紧密的关系，其中最小密度的最小化方案（即有效的方案）对应于小尺寸的通用击球集。本地方案是对最小化方案的概括，可将其用作最小化计划的替代，并有可能提高效率。我们建立了有效的本地方案与必须被通用击球集击中的字符串的最小长度之间的联系。我们为Mykkeltveit通用击球集的剩余路径长度提供了界限。此外，我们创建了一个局部方案，该方案具有最低的已知密度，这仅是远离理论下限的对数因子。
Universal hitting sets are sets of words that are unavoidable: every long enough sequence is hit by the set (i.e., it contains a word from the set). There is a tight relationship between universal hitting sets and minimizers schemes, where minimizers schemes with low density (i.e., efficient schemes) correspond to universal hitting sets of small size. Local schemes are a generalization of minimizers schemes which can be used as replacement for minimizers scheme with the possibility of being much more efficient. We establish the link between efficient local schemes and the minimum length of a string that must be hit by a universal hitting set. We give bounds for the remaining path length of the Mykkeltveit universal hitting set. Additionally, we create a local scheme with the lowest known density that is only a log factor away from the theoretical lower bound.
