概要 - スワップと置換による文字列の一致問題
タイトル
スワップと置換による文字列の一致問題
時間
2025-07-25 10:20:55
著者
{"Estéban Gabory","Laurent Bulteau","Gabriele Fici","Hilde Verbeek"}
カテゴリ
{cs.DS,cs.CC}
リンク
http://arxiv.org/abs/2507.19139v1
PDF リンク
http://arxiv.org/pdf/2507.19139v1
概要
この論文は、文字列のコンセンサス問題を調査し、特にClosest String問題に焦点を当てています。この問題の目的は、与えられた距離（ハミング距離などの距離）を最小化する文字列を見つけることです。論文は、これに隣接する文字の交換を除けば、置換の他に操作を許可することでこの問題を拡張しています。 論文の主な貢献は以下の通りです： 1. 著者たちは、交換と置換が許可されている場合でも、すべての入力文字列に対する最大距離を最小化する一般化問題はNP難であることを示しました。 2. その問題は、パラメータd（許可される最大距離）に関する固定パラメータ可解（FPT）であることを示しました。これは、入力のサイズに対して多項式時間で動作するアルゴリズムが存在することを意味します。 3. 著者たちは、出力文字列からすべての入力文字列への距離の和を最小化することを目指す問題のバリエーションを調査しました。このバリエーションに対する多項式時間アルゴリズムを提案しています。 論文では、Swap距離も考慮しています。Swap距離は、ある文字列を別の文字列に変換するのに必要な最小交換回数です。著者たちは、Swap距離のもとでのClosest String問題の半径のみのバリエーションがFPTであることを示し、和のみのバリエーションが多項式時間（P）であることを示しました。 全体的に、この論文は交換と置換を含む文字列のコンセンサス問題を包括的に分析し、これらの問題を解くための効率的なアルゴリズムを提案しています。
推奨論文
モバイルエッジコンピューションシステムにおけるデッドライン意識型のジョイントタスクスケジューリングおよびオフロード
相関と動的因果順序を持つ量子回路
ブロック符号化におけるアンシラ・オーバーヘッドを削減する方法
変額年金：リベット保証、ハイブリッド契約設計、および課税の詳細な見解
JWB-DH-V1：第1版 联合全身トーカングアバターや音声生成のベンチマーク
VisionThink：強化学習を通じてスマートで効率的な視覚言語モデル
「同等に有効なモデルからの任意の予測」
LOTUS: 質から社会偏りとユーザー好みに至る詳細な画像キャプションのためのリーダーボード
Pauli測定は単一杯子トモグラフィにおいてほぼ最適です。
バランスの乱れ：生成モデルにおけるオンライン概念バランス