License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.76
URN: urn:nbn:de:0030-drops-146574
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14657/
Go to the corresponding LIPIcs Volume Portal

Potępa, Krzysztof

Faster Deterministic Modular Subset Sum

pdf-format:
LIPIcs-ESA-2021-76.pdf (0.7 MB)

Abstract

We consider the Modular Subset Sum problem: given a multiset X of integers from ℤ_m and a target integer t, decide if there exists a subset of X with a sum equal to t (mod m). Recent independent works by Cardinal and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and near-linear algorithms for this problem. Cardinal and Iacono gave a randomized algorithm that runs in ?(m log m) time, while Axiotis et al. gave a deterministic algorithm that runs in ?(m polylog m) time. Both results work by reduction to a text problem, which is solved using a dynamic strings data structure.
In this work, we develop a simple data structure, designed specifically to handle the text problem that arises in the algorithms for Modular Subset Sum. Our data structure, which we call the shift-tree, is a simple variant of a segment tree. We provide both a hashing-based and a deterministic variant of the shift-trees.
We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is Monte-Carlo randomized and matches the ?(m log m) runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in ?(m log m ⋅ α(m)) time, where α is the inverse Ackermann function.

BibTeX - Entry

@InProceedings{potepa:LIPIcs.ESA.2021.76,
  author =	{Pot\k{e}pa, Krzysztof},
  title =	{{Faster Deterministic Modular Subset Sum}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14657},
  URN =		{urn:nbn:de:0030-drops-146574},
  doi =		{10.4230/LIPIcs.ESA.2021.76},
  annote =	{Keywords: Modular Subset Sum, String Problem, Segment Tree, Data Structure}
}

Keywords: Modular Subset Sum, String Problem, Segment Tree, Data Structure
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI