2026-07-23T20:12:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17956 2024-03-06T11:00:43Z ddc:004 open_access

Approximation Algorithms for the Longest Run Subsequence Problem Asahiro, Yuichi Eto, Hiroshi Gong, Mingyang Jansson, Jesper Lin, Guohui Miyano, Eiji Ono, Hirotaka Tanaka, Shunichi Longest run subsequence problem bounded occurrence approximation algorithm We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ⋯ s_n over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S^* of S such that the length |S^*| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time (k+1)/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 3/2 to 4/3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuichi Asahiro and Hiroshi Eto and Mingyang Gong and Jesper Jansson and Guohui Lin and Eiji Miyano and Hirotaka Ono and Shunichi Tanaka 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.2 urn:nbn:de:0030-drops-179560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode