論文の概要: Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals

• arxiv url: http://arxiv.org/abs/2601.16091v1
• Date: Thu, 22 Jan 2026 16:42:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-23 21:37:20.653009
• Title: Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals
• Title（参考訳）: 確率条件付きオンライン非セントロイドクラスタリングにおける遅延アサインメント
• Authors: Saar Cohen,
• Abstract要約: クラスタリングは基本的な問題であり、同じクラスタの要素が他のクラスタの要素よりも互いに近いように、一連の要素をクラスタに分割することを目指している。 オンライン非セントロイドクラスタリングを遅延で研究するための新しいフレームワークを提案し、有限距離空間の点として一度に1個ずつ到着する要素をクラスタに割り当てるが、割り当ては即時に行う必要はない。
• 参考スコア（独自算出の注目度）: 7.310043452300736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is a fundamental problem, aiming to partition a set of elements, like agents or data points, into clusters such that elements in the same cluster are closer to each other than to those in other clusters. In this paper, we present a new framework for studying online non-centroid clustering with delays, where elements, that arrive one at a time as points in a finite metric space, should be assigned to clusters, but assignments need not be immediate. Specifically, upon arrival, each point's location is revealed, and an online algorithm has to irrevocably assign it to an existing cluster or create a new one containing, at this moment, only this point. However, we allow decisions to be postponed at a delay cost, instead of following the more common assumption of immediate decisions upon arrival. This poses a critical challenge: the goal is to minimize both the total distance costs between points in each cluster and the overall delay costs incurred by postponing assignments. In the classic worst-case arrival model, where points arrive in an arbitrary order, no algorithm has a competitive ratio better than sublogarithmic in the number of points. To overcome this strong impossibility, we focus on a stochastic arrival model, where points' locations are drawn independently across time from an unknown and fixed probability distribution over the finite metric space. We offer hope for beyond worst-case adversaries: we devise an algorithm that is constant competitive in the sense that, as the number of points grows, the ratio between the expected overall costs of the output clustering and an optimal offline clustering is bounded by a constant.
• Abstract（参考訳）: クラスタ化は基本的な問題であり、エージェントやデータポイントといった一連の要素を、同じクラスタ内の要素が他のクラスタよりも互いに近いようにクラスタに分割することを目指している。 本稿では,オンライン非セントロイドクラスタリングを遅延で研究するための新しい枠組みを提案する。そこでは,有限距離空間の点として一度に1個ずつ到着する要素をクラスタに割り当てる必要があるが,割り当ては即座に行う必要はない。 具体的には、到着時に各ポイントの位置が明らかにされ、オンラインアルゴリズムはそれを既存のクラスタに無効に割り当てるか、あるいは現時点では、このポイントのみを含む新しいクラスタを作成する必要がある。 しかし、私たちは、到着時にすぐに決定されるというより一般的な仮定に従うのではなく、遅延コストで決定を延期することを許します。 目標は、各クラスタ内のポイント間の全距離コストと、割り当てを延期することで生じる全体の遅延コストを最小化することです。 任意の順に点が到着する古典的な最悪の到着モデルでは、点数において下位対数よりも競争率が高いアルゴリズムは存在しない。 この強い不可視性を克服するために、有限距離空間上の未知の確率分布と固定された確率分布から点の位置を時間的に独立に描画する確率到着モデルに焦点をあてる。 ポイントの数が増えるにつれて、アウトプットクラスタリングの期待される全体的なコストと最適なオフラインクラスタリングの比率が一定に制限されるという意味で、常に競合するアルゴリズムを考案する。

関連論文リスト

• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  本稿では,SCMax と呼ばれる自己教師型コンセンサス最大化による,新しい完全パラメータフリークラスタリングフレームワークを提案する。 本フレームワークは,階層的なクラスタリングとクラスタ評価を単一の統合プロセスで行う。
  論文  参考訳（メタデータ） (2025-11-12T11:17:17Z)
• Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
  一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。 そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
  論文  参考訳（メタデータ） (2024-10-16T18:00:19Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Neural Capacitated Clustering [6.155158115218501]
  本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。 人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
  論文  参考訳（メタデータ） (2023-02-10T09:33:44Z)
• Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints [0.0]
  均等なクラスタリングは、密度も期待されるクラスの数にも依存せず、相似性の閾値にも依存します。 このクラスタリング問題に対する様々な実践的ソリューション間のトレードオフを特定するために,適切なクラスタリングアルゴリズムをレビューし,評価する。
  論文  参考訳（メタデータ） (2021-09-28T12:02:18Z)
• Feature-based Individual Fairness in k-Clustering [14.847868952138795]
  公平性の制約を確保しつつ一組の点をクラスタリングする問題を考察する。 我々は、必ずしもクラスタリングに使用されない特徴に基づいて、kクラスタリングにおける個別の公平性という新しい概念を導入する。
  論文  参考訳（メタデータ） (2021-09-09T20:42:02Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Ball k-means [53.89505717006118]
  Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。 高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
  論文  参考訳（メタデータ） (2020-05-02T10:39:26Z)

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

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