Range Longest Increasing Subsequence and its Relatives
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908682505158656 |
|---|---|
| author | S., Karthik C. Rahul, Saladi |
| author_facet | S., Karthik C. Rahul, Saladi |
| contents | In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to RLIS is a sequence $S$ of $n$ real numbers and a collection $Q$ of $m$ query ranges, and for each query in $Q$, the goal is to report the LIS of the sequence $S$ restricted to that query. Our two main results are for the following generalizations of the RLIS problem.
2D range queries: In this variant of the RLIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide a randomized algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$, where $k$ is the cumulative length of the $m$ output subsequences. This improves on the elementary $O(mn)$-time algorithm when $m$ is at least $n^{1/2}$. Previously, the only known result breaking the quadratic barrier was due to Tiskin [SODA'10], which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length).
Colored sequences: In this variant of the RLIS problem, each element in $S$ is colored, and for each query in $Q$, the goal is to report a monochromatic LIS contained in the sequence $S$ restricted to that query. For 2D queries, we provide a randomized algorithm for this colored version with running time $\tilde{O}(m n^{2/3} + n^{5/3}) + O(k)$. Moreover, for 1D queries, we provide an improved algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$. Thus, we again improve on the elementary $O(mn)$-time algorithm. Additionally, assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, we prove that the running time for 1D queries is essentially tight for combinatorial algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04795 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Range Longest Increasing Subsequence and its Relatives S., Karthik C. Rahul, Saladi Data Structures and Algorithms In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to RLIS is a sequence $S$ of $n$ real numbers and a collection $Q$ of $m$ query ranges, and for each query in $Q$, the goal is to report the LIS of the sequence $S$ restricted to that query. Our two main results are for the following generalizations of the RLIS problem. 2D range queries: In this variant of the RLIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide a randomized algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$, where $k$ is the cumulative length of the $m$ output subsequences. This improves on the elementary $O(mn)$-time algorithm when $m$ is at least $n^{1/2}$. Previously, the only known result breaking the quadratic barrier was due to Tiskin [SODA'10], which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length). Colored sequences: In this variant of the RLIS problem, each element in $S$ is colored, and for each query in $Q$, the goal is to report a monochromatic LIS contained in the sequence $S$ restricted to that query. For 2D queries, we provide a randomized algorithm for this colored version with running time $\tilde{O}(m n^{2/3} + n^{5/3}) + O(k)$. Moreover, for 1D queries, we provide an improved algorithm with running time $\tilde{O}(m n^{1/2} + n^{3/2}) + O(k)$. Thus, we again improve on the elementary $O(mn)$-time algorithm. Additionally, assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, we prove that the running time for 1D queries is essentially tight for combinatorial algorithms. |
| title | Range Longest Increasing Subsequence and its Relatives |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.04795 |