論文の概要: 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法は時間的コストで最適解が得られるのに対し,メタヒューリスティック法はより合理的な計算コストで同等の解が得られることがわかった。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Using Constraints to Discover Sparse and Alternative Subgroup Descriptions [0.0]
  サブグループ発見法により、ユーザはデータセットで興味深い領域の簡単な記述を取得できる。 まず、サブグループ記述で使用される機能の数を制限し、後者はスパース化します。 第二に、与えられたサブグループと類似したデータオブジェクトの集合をカバーするが、異なる特徴を持つ代替サブグループ記述を見つけるための新しい最適化問題を提案する。
  論文  参考訳（メタデータ） (2024-06-03T15:10:01Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、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)
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
  群が閉部分群である同期問題のクラスを考える。 このような問題を解くための統一的なアプローチを提案する。 私たちのアプローチは既存のアプローチよりも優れています。
  論文  参考訳（メタデータ） (2020-09-16T07:25:50Z)

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

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