论文标题
模块化子集总和，动态字符串和零和零和集合
Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
论文作者
论文摘要
模块化子集总和问题包括决定，给定模量$ m $，一个$ n $ n $ $ n $整数的$ 0..m-1 $，以及目标整数$ t $，是否存在$ s $的子集，是否存在元素的子集，是否存在元素到$ t \ mod m $，并且报告了这样的设置。对于模块化子集总和问题，我们给出了一个简单的$ O（M \ log M）$ - 具有高概率（W.H.P.）算法的时间。这是基于以前的$ O（M \ log^7 m）$ W.H.P.的基础并改进的。来自Axiotis，Backurs，Jin，Tzamos和Wu的算法（Soda 19）。我们的方法利用了Gawrychowski等人的动态字符串结构的ADT。 （苏打〜18）。但是，由于这种结构相当复杂，因此我们提出了一种更简单的替代方案，我们称之为数据依赖性树。作为应用程序，我们考虑了零和拉姆西理论中基本定理的计算版本。 ERDőS-GINZBURG-ZIV定理指出，$ 2N-1 $整数的多键始终包含恰好$ N $的基数子集，其值总计为$ n $的倍数。我们提供了一种算法，用于在时间$ o（n \ log n）$ W.H.P.中找到这样的子集。由于Del Lungo，Marini和Mori（Disc。Math。09），它在$ O（N^2）$算法上有所改善。
The modular subset sum problem consists of deciding, given a modulus $m$, a multiset $S$ of $n$ integers in $0..m-1$, and a target integer $t$, whether there exists a subset of $S$ with elements summing to $t \mod m $, and to report such a set if it exists. We give a simple $O(m \log m)$-time with high probability (w.h.p.) algorithm for the modular subset sum problem. This builds on and improves on a previous $O(m \log^7 m)$ w.h.p. algorithm from Axiotis, Backurs, Jin, Tzamos, and Wu (SODA 19). Our method utilizes the ADT of the dynamic strings structure of Gawrychowski et al. (SODA~18). However, as this structure is rather complicated we present a much simpler alternative which we call the Data Dependent Tree. As an application, we consider the computational version of a fundamental theorem in zero-sum Ramsey theory. The Erdős-Ginzburg-Ziv Theorem states that a multiset of $2n - 1$ integers always contains a subset of cardinality exactly $n$ whose values sum to a multiple of $n$. We give an algorithm for finding such a subset in time $O(n \log n)$ w.h.p. which improves on an $O(n^2)$ algorithm due to Del Lungo, Marini, and Mori (Disc. Math. 09).
