Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
In the minimum common string partition problem (MCSP), one gets two strings and is asked to find the minimum number of cuts in the first string such that the second string can be obtained by rearranging the resulting pieces. It is a difficult algorithmic problem having applications in computational biology, text processing, and data compression. MCSP has been studied extensively from various algorithmic angles: there are many papers studying approximation, heuristic, and parameterized algorithms. At the same time, almost nothing is known about its exact complexity. In this paper, we present new results in this direction. We improve the known 2n upper bound (where n is the length of input strings) to ϕn where ϕ ≈ 1.618... is the golden ratio. The algorithm uses Fibonacci numbers to encode subsets as monomials of a certain implicit polynomial and extracts one of its coefficients using the fast Fourier transform. Then, we show that the case of constant size alphabet can be solved in subexponential time 2O(n log log n/log n) by a hybrid strategy: enumerate all long pieces and use dynamic programming over histograms of short pieces. Finally, we prove almost matching lower bounds assuming the Exponential Time Hypothesis.
Язык оригинала | английский |
---|---|
Название основной публикации | 29th Annual European Symposium on Algorithms, ESA 2021 |
Редакторы | Petra Mutzel, Rasmus Pagh, Grzegorz Herman |
Издатель | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
ISBN (электронное издание) | 9783959772044 |
DOI | |
Состояние | Опубликовано - 1 сен 2021 |
Событие | 29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Португалия Продолжительность: 6 сен 2021 → 8 сен 2021 |
Название | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Том | 204 |
ISSN (печатное издание) | 1868-8969 |
конференция | 29th Annual European Symposium on Algorithms, ESA 2021 |
---|---|
Страна/Tерритория | Португалия |
Город | Vitual, Lisbon |
Период | 6/09/21 → 8/09/21 |
ID: 97553114