DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2023.2

Approximation Algorithms for the Longest Run Subsequence Problem

Authors: Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract

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.

Cite as

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2,
  author =	{Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi},
  title =	{{Approximation Algorithms for the Longest Run Subsequence Problem}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2},
  URN =		{urn:nbn:de:0030-drops-179560},
  doi =		{10.4230/LIPIcs.CPM.2023.2},
  annote =	{Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2022.53

Approximation Algorithms for Covering Vertices by Long Paths

Authors: Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.

Cite as

Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano. Approximation Algorithms for Covering Vertices by Long Paths. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gong_et_al:LIPIcs.MFCS.2022.53,
  author =	{Gong, Mingyang and Fan, Jing and Lin, Guohui and Miyano, Eiji},
  title =	{{Approximation Algorithms for Covering Vertices by Long Paths}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.53},
  URN =		{urn:nbn:de:0030-drops-168517},
  doi =		{10.4230/LIPIcs.MFCS.2022.53},
  annote =	{Keywords: Path cover, k-path, local improvement, amortized analysis, approximation algorithm}
}

Search Results

Documents authored by Gong, Mingyang

Approximation Algorithms for the Longest Run Subsequence Problem

Abstract

Cite as

Approximation Algorithms for Covering Vertices by Long Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message