論文の概要: Clustered Orienteering Problem with Subgroups
- arxiv url: http://arxiv.org/abs/2312.16154v2
- Date: Wed, 27 Dec 2023 16:24:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 20:43:53.852717
- Title: Clustered Orienteering Problem with Subgroups
- Title(参考訳): 部分群によるクラスタ化配向問題
- Authors: Luciano E. Almeida and Douglas G. Macharet
- Abstract要約: サブグループによるクラスター配向問題(COPS)
我々の新しい定式化は、以前の2つのよく知られた変種をモデル化し、解決する能力を持っていることを示す。
- 参考スコア(独自算出の注目度): 6.961946145048321
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces an extension to the Orienteering Problem (OP), called
Clustered Orienteering Problem with Subgroups (COPS). In this variant, nodes
are arranged into subgroups, and the subgroups are organized into clusters. A
reward is associated with each subgroup and is gained only if all of its nodes
are visited; however, at most one subgroup can be visited per cluster. The
objective is to maximize the total collected reward while attaining a travel
budget. We show that our new formulation has the ability to model and solve two
previous well-known variants, the Clustered Orienteering Problem (COP) and the
Set Orienteering Problem (SOP), in addition to other scenarios introduced here.
An Integer Linear Programming (ILP) formulation and a Tabu Search-based
heuristic are proposed to solve the problem. Experimental results indicate that
the ILP method can yield optimal solutions at the cost of time, whereas the
metaheuristic produces comparable solutions within a more reasonable
computational cost.
- Abstract(参考訳): 本稿では,OP(Clustered Orienteering Problem with Subgroups, COPS)の拡張について述べる。
この変種では、ノードはサブグループに配置され、サブグループはクラスタに編成される。
報酬は各サブグループに関連付けられ、すべてのノードが訪問される場合にのみ得られるが、少なくとも1つのサブグループをクラスタごとに訪問することができる。
目的は、旅行予算を達成しながら収集した報酬を最大化することである。
我々の新しい定式化は、ここで紹介された他のシナリオに加えて、以前のよく知られた2つの変種であるクラスタ指向問題(COP)とセット指向問題(SOP)をモデル化し、解決する能力を持っていることを示す。
Integer Linear Programming (ILP) の定式化と Tabu Search に基づくヒューリスティックを提案する。
実験の結果,ILP法は時間的コストで最適解が得られるのに対し,メタヒューリスティック法はより合理的な計算コストで同等の解が得られることがわかった。
関連論文リスト
- Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Optimal Clustering with Bandit Feedback [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳(メタデータ) (2022-02-01T19:31:15Z) - Personalized Federated Learning via Convex Clustering [72.15857783681658]
本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。
提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
論文 参考訳(メタデータ) (2022-02-01T19:25:31Z) - Interpretable Clustering via Multi-Polytope Machines [12.69310440882225]
本稿では,クラスタデータポイントと,検出したクラスタの周辺にポリトープを構築して説明する,解釈可能なクラスタリングのための新しい手法を提案する。
我々は,我々の手法を,人工クラスタリングと実世界のクラスタリングの一連の問題にベンチマークし,我々のアルゴリズムは,アート解釈可能で非解釈可能なクラスタリングアルゴリズムの状態を上回ります。
論文 参考訳(メタデータ) (2021-12-10T16:36:32Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Robust subgroup discovery [0.2578242050187029]
最小記述長原理を用いて最適ロバスト部分群発見の問題を定式化する。
RSDは、良いサブグループリストを見つけ、各イテレーションで最も重要なサブグループが追加されたことを保証します。
我々は,rsdが従来のサブグループ集合発見法を上回っている54のデータセットを,品質とサブグループリストサイズの観点から実証的に示す。
論文 参考訳(メタデータ) (2021-03-25T09:04:13Z) - Clustering with Penalty for Joint Occurrence of Objects: Computational
Aspects [0.0]
Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。
この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。
本稿では,本手法の計算的側面について考察する。
論文 参考訳(メタデータ) (2021-02-02T10:39:27Z) - Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
本稿では,複数のクラスタリングを組み合わせ,個々のクラスタリングよりも優れたパフォーマンスを実現するクラスタリングアンサンブルの問題について検討する。
本稿では,この問題をグローバルな視点から解くために,新しい低ランクテンソル近似法を提案する。
7つのベンチマークデータセットを用いた実験の結果,提案手法は12の最先端手法と比較して,クラスタリング性能のブレークスルーを達成した。
論文 参考訳(メタデータ) (2020-12-16T13:01:37Z) - A Unified Approach to Synchronization Problems over Subgroups of the
Orthogonal Group [29.714239628405515]
群が閉部分群である同期問題のクラスを考える。
このような問題を解くための統一的なアプローチを提案する。
私たちのアプローチは既存のアプローチよりも優れています。
論文 参考訳(メタデータ) (2020-09-16T07:25:50Z) - Probabilistic Fair Clustering [31.628993679745292]
フェアクラスタリングにおける以前の仕事は、グループメンバーシップの完全な知識を前提としている。
近似比を保証したより一般的な設定でクラスタリングアルゴリズムを提案する。
また、異なる群が順序と距離の概念を持つ「計量的メンバーシップ」の問題にも対処する。
論文 参考訳(メタデータ) (2020-06-19T01:34:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。