論文の概要: Improved approximation algorithms for capacitated cluster editing

• arxiv url: http://arxiv.org/abs/2611.05916v1
• Date: Wed, 04 Nov 2026 04:12:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:57.938196
• Title: Improved approximation algorithms for capacitated cluster editing
• Title（参考訳）: 容量化クラスタ編集のための近似アルゴリズムの改良
• Abstract要約: 完全エッジ符号グラフを用いた最小分散クラスタ編集問題について検討する。 候補クリッドのサイズが非有界であるとき、問題はNPハードとAPXハードである。 その結果, フラクチャ95 L + フラクチャ110 OPT_k$で, 通常のピボットを用いたハイブリッドは, 高いコストが期待できることがわかった。
• 参考スコア（独自算出の注目度）: 6.439173290341198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of $α= 1.3865 + ε$. The capacitated variant, in which the candidate cliques have sizes no greater than a given $k$, is less studied and the best approximation ratio is $5.37$. In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of $α_k = 2 α+ 1$, based on any $α$-approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost $L$, the hybrid using ordinary pivoting has an expected cost at most $\frac 95 L + \frac 1{10} \OPT_k$, and the hybrid using conditional pivoting has an expected cost at most $\frac {306}{203} L + \frac {50}{203} \OPT_k$. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized $(1.9 + ε)$-approximation algorithm and a randomized $(1.7537 + ε)$-approximation algorithm, respectively.
• Abstract（参考訳）: 正のエッジが互いに一致する2つの頂点を表すが、負のエッジが不一致を表すような完全エッジ符号グラフから、斜め内の負のエッジの総数と斜めの外の正のエッジが最小となるような、上界の大きさの非結合な傾斜を構成できる最小分散クラスタ編集問題について検討する。 候補の傾きの大きさが非有界の場合、問題はNP-hardとAPX-hardであり、文献や最先端の近似比である$α=1.3865 + ε$で改善された多くの近似アルゴリズムが提案されている。 キャパシタイトされた変種は、候補の傾きが与えられた$k$以上の大きさを持つが、研究は少なく、最適な近似比は5.37$である。 本稿では,後者の問題について考察する。 まず, キャパシタ付き問題に対する任意の$α$-近似アルゴリズムに基づいて, 近似比を$α_k = 2 α+ 1$とするダウンサイズ手法を提案する。 次に、クラスタ-LPサンプリングとピボットのハイブリッドを提案し、通常のピボットを用いたハイブリッドは、最大$\frac 95 L + \frac 1{10} \OPT_k$で、条件ピボットを用いたハイブリッドは最大$\frac {306}{203} L + \frac {50}{203} \OPT_k$で、通常のピボットを用いたハイブリッドは最大$\frac 95 L + \frac 1{10} \OPT_k$で、予測コストは最大$\frac {306}{203} L + \frac {50}{203} \OPT_k$であることを示した。 García-Soriano と Schohn の近似二分法フレームワークの濃度制約適応は、必要な分数解を提供し、ランダム化された$(1.9 + ε)$-approximationアルゴリズムとランダム化された$(1.7537 + ε)$-approximationアルゴリズムをそれぞれ得る。

関連論文リスト

• A Sub-4 Approximation for Fair $k$-Means [18.61347737579578]
  ユークリッド空間における公平な$k$-meansクラスタリングについて検討し、各クラスタにおける保護群の割合は、指定された下限と上限内にある必要がある。 本稿では,線形プログラミング緩和と入力の幾何学変換を組み合わせた近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-09-07T20:54:36Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• Multilayer Correlation Clustering [12.492037397168579]
  相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。 本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。 目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
  論文  参考訳（メタデータ） (2024-04-25T15:25:30Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。
  論文  参考訳（メタデータ） (2023-10-13T03:08:59Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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