Approximation Algorithms for the Longest Run Subsequence Problem
Approximation Algorithms for the Longest Run Subsequence Problem
复制标题
DOI：
10.4230/lipics.cpm.2023.2
复制
发表时间：
2023
期刊：
影响因子：
12.3
通讯作者：
Y. Asahiro;Hiroshi Eto;Mingyang Gong;J. Jansson;Guohui Lin;Eiji Miyano;H. Ono;Shunichi Tanaka
中科院分区：
文献类型：
--
作者：
Y. Asahiro;Hiroshi Eto;Mingyang Gong;J. Jansson;Guohui Lin;Eiji Miyano;H. Ono;Shunichi Tanaka
我们研究了最长运行子序列问题（简称LRS）的逼近性。对于字母表 Σ 上的字符串 S = s 1 · · · s n ，S 中符号 σ ∈ Σ 的游程是 σ 连续出现的最大子串。 S 的游程子序列 S ' 是其中每个符号 σ ∈ Σ 最多出现在一次游程中的序列。给定一个字符串 S ，LRS 的目标是找到 S 的最长运行子序列 S * ，使得长度 | S*|在 S 的所有运行子序列上最大化。众所周知，即使每个符号在输入字符串中最多出现两次，LRS 也是 APX-hard，并且如果输入字符串中每个符号的出现次数以 k 为界，则 LRS 承认多项式时间 k 近似算法。在本文中，我们在输入字符串的 k 次出现约束下设计了 LRS 的多项式时间 k +12 逼近算法。对于k = 2的情况，我们进一步将近似比从32提高到43。
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 +12 -approximation algorithm for LRS under the k -occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 32 to 43 .