論文の概要: The Small Solution Hypothesis for MAPF on Directed Graphs Is True
- arxiv url: http://arxiv.org/abs/2210.04590v1
- Date: Mon, 10 Oct 2022 11:51:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 18:58:51.916222
- Title: The Small Solution Hypothesis for MAPF on Directed Graphs Is True
- Title(参考訳): 方向グラフ上のMAPFの小さな解仮説は真である
- Authors: Bernhard Nebel
- Abstract要約: 有向グラフ上のマルチエージェントパスフィンディングの計算複雑性の決定は、長年にわたり未解決の問題であった。
つい最近になって、問題はNPハードであることが証明された。
- 参考スコア(独自算出の注目度): 6.304912477609385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The determination of the computational complexity of multi-agent pathfinding
on directed graphs has been an open problem for many years. Only recently, it
has been established that the problem is NP-hard. Further, it has been proved
that it is in NP, provided the short solution hypothesis for strongly connected
digraphs holds. In this paper, it is shown that this hypothesis is indeed true.
- Abstract(参考訳): 有向グラフ上のマルチエージェントパスフィンディングの計算複雑性の決定は、長年にわたり未解決の問題であった。
最近になって、問題はnp-hardであることが判明した。
さらに、強く連結されたダイグラフの短い解仮説が成り立つと、NP内であることが証明されている。
本稿では,この仮説が真であることを示す。
関連論文リスト
- Testing Dependency of Weighted Random Graphs [4.0554893636822]
本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。
一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
論文 参考訳(メタデータ) (2024-09-23T10:07:41Z) - Graph Stochastic Neural Process for Inductive Few-shot Knowledge Graph Completion [63.68647582680998]
I-FKGC(inductive few-shot knowledge graph completion)と呼ばれる課題に焦点をあてる。
帰納的推論(inductive reasoning)の概念に着想を得て,I-FKGCを帰納的推論問題とした。
本稿では,仮説の連成分布をモデル化したニューラルプロセスに基づく仮説抽出器を提案する。
第2のモジュールでは、この仮説に基づいて、クエリセットのトリプルが抽出された仮説と一致するかどうかをテストするグラフアテンションベースの予測器を提案する。
論文 参考訳(メタデータ) (2024-08-03T13:37:40Z) - Large Language Model for Science: A Study on P vs. NP [88.67249044141529]
大規模言語モデル(LLM)を用いて,P対NP問題の研究を促進・促進する。
具体的には、複雑な問題解決のためのLLMを用いた奥行き思考を促進する一般的なフレームワークであるソクラティック推論を提案する。
我々のP対NP問題に関するパイロット研究は、GPT-4が証明スキーマの生成に成功し、97の対話ターンを通して厳密な推論を行うことを示した。
論文 参考訳(メタデータ) (2023-09-11T17:49:27Z) - On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions [1.5675763601034223]
双分極問題は、重み付きラベル付きグラフ上で最も高い偏極二分法を見つけることを目標とする最適化問題である。
単一パラメータがインスタンスの分極を制御するインスタンス生成モデルを導入する。
論文 参考訳(メタデータ) (2023-07-21T14:40:41Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳(メタデータ) (2023-05-22T17:43:34Z) - The (Un)Scalability of Heuristic Approximators for NP-Hard Search
Problems [25.641418039598587]
A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。
このような問題の多くに対する正確な近似もNPハードであることを示す。
論文 参考訳(メタデータ) (2022-09-07T18:02:02Z) - Influence Maximization (IM) in Complex Networks with Limited Visibility
Using Statistical Methods [2.320417845168326]
影響文学(IM)問題はNP完全問題(NP完全問題)として知られており、時間内に解が存在しない。
この複雑さを改善するために提案された手法のほとんどは、グラフ全体が見えるという仮定に基づいている。
本研究では,リンク予測手法による現在の手法を擬似可視グラフに拡張する。
論文 参考訳(メタデータ) (2022-08-28T07:55:54Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳(メタデータ) (2021-10-12T02:21:30Z) - Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
機械学習理論における中心的な問題は、ゼロエラーを持つ一貫した仮説を効率的に見つけることができるかどうかである。
このアルゴリズムの一般的な考え方は、弱凸仮説の場合にまで拡張可能であることを示す。
論文 参考訳(メタデータ) (2021-05-10T23:00:02Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳(メタデータ) (2020-11-04T10:25:13Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。