Improved Lower Bounds on the Expected Length of Longest Common Subsequences
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916324770316288 |
|---|---|
| author | Heineman, George T. Miller, Chase Reichman, Daniel Salls, Andrew Sárközy, Gábor Soiffer, Duncan |
| author_facet | Heineman, George T. Miller, Chase Reichman, Daniel Salls, Andrew Sárközy, Gábor Soiffer, Duncan |
| contents | It has been proven that, when normalized by $n$, the expected length of a longest common subsequence of $d$ random strings of length $n$ over an alphabet of size $σ$ converges to some constant that depends only on $d$ and $σ$. These values are known as the Chvátal-Sankoff constants, and determining their exact values is a well-known open problem. Upper and lower bounds are known for some combinations of $σ$ and $d$, with the best lower and upper bounds for the most studied case, $σ=2, d=2$, at $0.788071$ and $0.826280$, respectively. Building off previous algorithms for lower-bounding the constants, we implement runtime optimizations, parallelization, and an efficient memory reading and writing scheme to obtain an improved lower bound of $0.792665992$ for $σ=2, d=2$. We additionally improve upon almost all previously reported lower bounds for the Chvátal-Sankoff constants when either the size of alphabet, the number of strings, or both are larger than 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10925 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Lower Bounds on the Expected Length of Longest Common Subsequences Heineman, George T. Miller, Chase Reichman, Daniel Salls, Andrew Sárközy, Gábor Soiffer, Duncan Data Structures and Algorithms It has been proven that, when normalized by $n$, the expected length of a longest common subsequence of $d$ random strings of length $n$ over an alphabet of size $σ$ converges to some constant that depends only on $d$ and $σ$. These values are known as the Chvátal-Sankoff constants, and determining their exact values is a well-known open problem. Upper and lower bounds are known for some combinations of $σ$ and $d$, with the best lower and upper bounds for the most studied case, $σ=2, d=2$, at $0.788071$ and $0.826280$, respectively. Building off previous algorithms for lower-bounding the constants, we implement runtime optimizations, parallelization, and an efficient memory reading and writing scheme to obtain an improved lower bound of $0.792665992$ for $σ=2, d=2$. We additionally improve upon almost all previously reported lower bounds for the Chvátal-Sankoff constants when either the size of alphabet, the number of strings, or both are larger than 2. |
| title | Improved Lower Bounds on the Expected Length of Longest Common Subsequences |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.10925 |