{"ID":2888713,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.22486","arxiv_id":"2507.22486","title":"Deterministic Longest Common Subsequence Approximation in Near-Linear Time","abstract":"We provide a deterministic algorithm that outputs an $O(n^{3/4} \\log n)$-approximation for the Longest Common Subsequence (LCS) of two input sequences of length $n$ in near-linear time. This is the first deterministic approximation algorithm for LCS that achieves a sub-linear approximation ratio in near-linear time.","short_abstract":"We provide a deterministic algorithm that outputs an $O(n^{3/4} \\log n)$-approximation for the Longest Common Subsequence (LCS) of two input sequences of length $n$ in near-linear time. This is the first deterministic approximation algorithm for LCS that achieves a sub-linear approximation ratio in near-linear time.","url_abs":"https://arxiv.org/abs/2507.22486","url_pdf":"https://arxiv.org/pdf/2507.22486v1","authors":"[\"Itai Boneh\",\"Shay Golan\",\"Matan Kraus\"]","published":"2025-07-30T08:45:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}