論文の概要: Sorting by Strip Swaps is NP-Hard

• arxiv url: http://arxiv.org/abs/2511.00015v1
• Date: Mon, 20 Oct 2025 15:51:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-09 16:58:40.029587
• Title: Sorting by Strip Swaps is NP-Hard
• Title（参考訳）: ストリップスワップによるソルティングはNPハードである
• Authors: Swapnoneel Roy, Asai Asaithambi, Debajyoti Mukhopadhyay,
• Abstract要約: ストリップスワップ(SbSS)によるemphSortingは,emphBlock Sortingの低減によってNPハードであることが示されている。 鍵となるアイデアは、地元のガジェット、Emphcageだ。
• 参考スコア（独自算出の注目度）: 0.6423239719448169
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that \emph{Sorting by Strip Swaps} (SbSS) is NP-hard by a polynomial reduction of \emph{Block Sorting}. The key idea is a local gadget, a \emph{cage}, that replaces every decreasing adjacency $(a_i,a_{i+1})$ by a guarded triple $a_i,m_i,a_{i+1}$ enclosed by guards $L_i,U_i$, so the only decreasing adjacencies are the two inside the cage. Small \emph{hinge} gadgets couple adjacent cages that share an element and enforce that a strip swap that removes exactly two adjacencies corresponds bijectively to a block move that removes exactly one decreasing adjacency in the source permutation. This yields a clean equivalence between exact SbSS schedules and perfect block schedules, establishing NP-hardness.
• Abstract（参考訳）: ストリップスワップによるemph{Sorting by Strip Swaps} (SbSS) が NP-hard であることを示す。 鍵となるアイデアは、ローカルガジェットのa \emph{cage}であり、これは、(a_i,a_{i+1})$をガード付き3重の$a_i,m_i,a_{i+1}$に置き換える。 小さな \emph{hinge} ガジェットは、隣り合うケージが要素を共有し、正確に2つの隣接を除去するストリップスワップが、ソース置換においてちょうど1つの減少する隣接を除去するブロック移動に対応することを強制する。 これにより、正確なSbSSスケジュールと完全なブロックスケジュールの間にクリーンな等価性が得られ、NPハードネスが確立される。

関連論文リスト

• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
  論文  参考訳（メタデータ） (2021-05-24T07:19:01Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon [88.75843804630772]
  エピソード強化学習は文脈的包帯を一般化する。 長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。 MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
  論文  参考訳（メタデータ） (2020-09-28T17:52:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。