| Item type |
SIG Technical Reports(1) |
| 公開日 |
2023-05-03 |
| タイトル |
|
|
タイトル |
最長ラン部分文字列問題に対する近似アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Approximation Algorithms for the Longest Run Subsequence Problem |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Kyushu Sangyo University |
| 著者所属 |
|
|
|
Kyushu Institute of Technology |
| 著者所属 |
|
|
|
Uniersity of Alberta |
| 著者所属 |
|
|
|
Kyoto University |
| 著者所属 |
|
|
|
Uniersity of Alberta |
| 著者所属 |
|
|
|
Kyushu Institute of Technology |
| 著者所属 |
|
|
|
Nagoya University |
| 著者所属 |
|
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Sangyo University |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Uniersity of Alberta |
| 著者所属(英) |
|
|
|
en |
|
|
Kyoto University |
| 著者所属(英) |
|
|
|
en |
|
|
Uniersity of Alberta |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者名 |
朝廣, 雄一
江藤, 宏
Gong, Mingyang
Jansson, Jesper
Lin, Guohui
宮野, 英次
小野, 廣隆
田中, 駿一
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本稿では，最長ラン部分文字列問題（LRS）の近似可能性について考える．ランは，連続する同じ文字の極大部分文字列のことである．文字集合 Σ 上の文字列 S=s1...sn に対し，S のラン部分文字列 S′はすべての文字 σ ∈ Σ について，高々 1 つのランで構成される部分文字列である．LRS は，文字列 S が与えられたとき，S のすべてのラン部分文字列の中で最長となるラン部分文字列 S* を求める最適化問題である．LRS は，入力文字列の各文字の出現数が高々 2 回の時でさえ APX 困難であることが知られている.また，入力文字列の各文字の出現数が高々 k 回の時，多項式時間で動作する k 近似アルゴリズムが存在することも知られている．本稿では，入力文字列の各文字の出現数が k 回までに制限されている LRS に対して，多項式時間で動作する k+1/2 近似アルゴリズムを設計する．さらに，k=2 の場合，近似率を 3/2 から 4/3 に改善する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We study the approximability of the Longest Run Subsequence problem (LRS for short). A run is a maximal substring of consecutive identical symbols. For a string S = s1...sn over an alphabet Σ, a run subsequence S′of S is a subsequence that contains at most one run for every symbol σ ∈ Σ. Given a string S, the goal of LRS is to find a longest run subsequence S* of S such that length |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2023-AL-193,
号 9,
p. 1-5,
発行日 2023-05-03
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL23193009.pdf (224.8 kB)
