論文の概要: Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach

• arxiv url: http://arxiv.org/abs/2601.11883v1
• Date: Sat, 17 Jan 2026 02:39:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.356936
• Title: Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach
• Title（参考訳）: 制約付き$k$-Centerクラスタリングの近似アルゴリズム:局所探索手法
• Authors: Chaoqi Jia, Longkun Guo, Kewen Liao, Zhigang Lu, Chao Chen, Jason Xue,
• Abstract要約: 本稿では,制約付きk中心クラスタリング問題について検討し,インスタンスレベルのNot-link (CL) と must-link (ML) の制約を背景知識として組み込む。 2 の近似比を最適に達成し,支配的集合問題への変換に基づく新しい局所探索フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 10.257446766550862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.
• Abstract（参考訳）: クラスタリングは長年の研究課題であり、AIとデータ分析の基本的なツールである。 クラスタリングの基本的な理論的課題である伝統的なk中心問題は、2の近似比が最適であり、2 - ε の比への改善は P = NP を意味する。 本研究では,制約付きk-centerクラスタリング問題について検討し,インスタンスレベルのNot-link (CL) と must-link (ML) の制約を背景知識として組み込む。 一般の CL の制約は近似の硬さを著しく増大させるが、以前の研究は不連結な CL 集合が定数要素近似を許すことを示した。 しかし、そのような保証をローカル検索が達成できるかどうかは未解決のままである。 そこで本研究では, 最良近似比2を達成し, 支配的集合問題への変換に基づく新しい局所探索フレームワークを提案する。 実世界のデータセットと合成データセットの両方の実験結果から,我々のアルゴリズムは解品質のベースラインよりも優れていることが示された。

関連論文リスト

• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。 制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
  論文  参考訳（メタデータ） (2024-01-23T07:16:32Z)
• Neural Capacitated Clustering [6.155158115218501]
  本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。 人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
  論文  参考訳（メタデータ） (2023-02-10T09:33:44Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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