論文の概要: Location-Aware Dispersion on Anonymous Graphs

• arxiv url: http://arxiv.org/abs/2602.05948v1
• Date: Thu, 05 Feb 2026 18:02:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 08:17:41.206607
• Title: Location-Aware Dispersion on Anonymous Graphs
• Title（参考訳）: 匿名グラフ上の位置認識分散
• Authors: Himani, Supantha Pandit, Gokarna Sharma,
• Abstract要約: よく研究された分散分散ロボットにおける基本的な協調問題である。 位置認識を取り入れた新しい分散の一般化であるLOOCATION-AWARE DisPERSIONを紹介する。 我々は,時間とメモリの双方の要求条件が保証されるようないくつかの決定論的アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 0.6253101769618639
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The well-studied DISPERSION problem is a fundamental coordination problem in distributed robotics, where a set of mobile robots must relocate so that each occupies a distinct node of a network. DISPERSION assumes that a robot can settle at any node as long as no other robot settles on that node. In this work, we introduce LOCATION-AWARE DISPERSION, a novel generalization of DISPERSION that incorporates location awareness: Let $G = (V, E)$ be an anonymous, connected, undirected graph with $n = |V|$ nodes, each labeled with a color $\sf{col}(v) \in C = \{c_1, \dots, c_t\}, t\leq n$. A set $R = \{r_1, \dots, r_k\}$ of $k \leq n$ mobile robots is given, where each robot $r_i$ has an associated color $\mathsf{col}(r_i) \in C$. Initially placed arbitrarily on the graph, the goal is to relocate the robots so that each occupies a distinct node of the same color. When $|C|=1$, LOCATION-AWARE DISPERSION reduces to DISPERSION. There is a solution to DISPERSION in graphs with any $k\leq n$ without knowing $k,n$. Like DISPERSION, the goal is to solve LOCATION-AWARE DISPERSION minimizing both time and memory requirement at each agent. We develop several deterministic algorithms with guaranteed bounds on both time and memory requirement. We also give an impossibility and a lower bound for any deterministic algorithm for LOCATION-AWARE DISPERSION. To the best of our knowledge, the presented results collectively establish the algorithmic feasibility of LOCATION-AWARE DISPERSION in anonymous networks and also highlight the challenges on getting an efficient solution compared to the solutions for DISPERSION.
• Abstract（参考訳）: 分散ロボティクスにおけるよく研究された分散分散分散処理問題では、移動ロボットの集合がネットワークの各ノードを占有するように移動する必要がある。 分散は、他のどのロボットもそのノードに落ち着かない限り、ロボットがどのノードに落ち着くことができると仮定する。 LOCATION-AWARE DisPERSIONは、位置認識を包含する新しい分散の一般化である:$G = (V, E)$を匿名で連結で無向グラフとし、$n = |V|$ノードとし、それぞれに色 $\sf{col}(v) \in C = \{c_1, \dots, c_t\}, t\leq n$ をラベル付けする。 a set $R = \{r_1, \dots, r_k\}$ of $k \leq n$ mobile robot, where each robot $r_i$ have a associated color $\mathsf{col}(r_i) \in C$。 当初、グラフ上に任意に配置された目標は、それぞれが同じ色の異なるノードを占有するように、ロボットを移動させることである。 C|=1$のとき、LOCATION-AWARE 分散は分散に還元される。 グラフにおける Dispersion の解は、$k,n$ を知らずに任意の$k\leq n$ を持つ。 DisPERSIONと同様に、目的は各エージェントにおける時間とメモリの要求を最小化するLOCATION-AWARE DisPERSIONを解決することである。 我々は,時間とメモリの双方の要求条件が保証されるようないくつかの決定論的アルゴリズムを開発した。 また、LOCATION-AWARE DisPERSIONのための決定論的アルゴリズムに対して、不確実性と低いバウンダリを与える。 この結果から, 匿名ネットワークにおけるLOCATION-AWARE DisPERSIONのアルゴリズム実現可能性を確立し, 分散の解よりも効率的な解を得る上での課題を強調した。

関連論文リスト

• Min-Sum Uniform Coverage Problem by Autonomous Mobile Robots [0.2446672595462589]
  移動ロボット群におけるテクスチミンサム一様被覆問題について検討した。 ロボットは動きを調整し、全ロボットが移動する総量を最小化する均一な空間に到達しなければならない。 本稿では,最小総移動コストのラインセグメンテーション設定において一様カバレッジを実現する決定論的分散アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-02-11T18:38:24Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing [28.977968088499566]
  我々は,各ノードが未知のラベルを持つような$n$-node graph $mathcalG$上で,逐次決定問題を研究する。 我々は、一般的なグラフに適用可能なGittinsインデックスベースのポリシーを設計し、$mathcalG$がフォレストである場合に確実に最適である。
  論文  参考訳（メタデータ） (2025-05-27T18:48:42Z)
• Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
  ラベルなしの動作計画では、衝突回避を確保しながら、ロボットのセットを目標の場所に割り当てる。 この問題は、探査、監視、輸送などの応用において、マルチロボットシステムにとって不可欠なビルディングブロックを形成している。 この問題に対処するために、各ロボットは、その400ドルのアネレストロボットと$k$アネレストターゲットの位置のみを知っている分散環境で対処する。
  論文  参考訳（メタデータ） (2024-09-29T23:57:25Z)
• Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
  本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。 私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。 目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
  論文  参考訳（メタデータ） (2023-08-14T08:52:24Z)
• The Sample Complexity of Online Contract Design [120.9833763323407]
  オンライン環境での隠れアクションの主エージェント問題について検討する。 各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。 エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
  論文  参考訳（メタデータ） (2022-11-10T17:59:42Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)

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

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