論文の概要: Average Case Graph Searching in Non-Uniform Cost Models
- arxiv url: http://arxiv.org/abs/2603.17916v1
- Date: Wed, 18 Mar 2026 16:54:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-19 18:32:57.831876
- Title: Average Case Graph Searching in Non-Uniform Cost Models
- Title（参考訳）: 非均一コストモデルにおける平均ケースグラフ検索
- Authors: Michał Szyfelbein,
- Abstract要約: 目標は、平均的な検索コストを最小限に抑える検索戦略を設計することである。
木を考慮し、$c(v, x)$ を単調な非減少関数と仮定する。
これは両基準に対する最初の定数係数近似アルゴリズムである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the following generalization of the classic Binary Search Problem: a searcher is required to find a hidden target vertex $x$ in a graph $G$, by iteratively performing queries about vertices. A query to $v$ incurs a cost $c(v, x)$ and responds whether $v=x$ and if not, returns the connected component in $G-v$ containing $x$. The goal is to design a search strategy that minimizes the average-case search cost. Firstly, we consider the case when the cost of querying a vertex is independent of the target. We develop a $\br{4+ε}$-approximation FPTAS for trees running in $O(n^4/ε^2)$ time and an $O({\sqrt{\log n}})$-approximation for general graphs. Additionally, we give an FPTAS parametrized by the number of non-leaf vertices of the graph. On the hardness side we prove that the problem is NP-hard even when the input is a tree with bounded degree or bounded diameter. Secondly, we consider trees and assume $c(v, x)$ to be a monotone non-decreasing function with respect to $x$, i.e.\ if $u \in P_{v, x}$ then $c(u, x) \leq c(v, x)$. We give a $2$-approximation algorithm which can also be easily altered to work for the worst-case variant. This is the first constant factor approximation algorithm for both criterions. Previously known results only regard the worst-case search cost and include a parametrized PTAS as well as a $4$-approximation for paths. At last, we show that when the cost function is an arbitrary function of the queried vertex and the target, then the problem does not admit any constant factor approximation under the UGC, even when the input tree is a star.
- Abstract（参考訳）: 検索者は、頂点に関するクエリを反復的に実行することにより、グラフ$G$で隠れたターゲットの頂点を$x$で見つける必要がある。
v$への問い合わせは$c(v, x)$を発生させ、$v=x$としない場合は$x$を含む$G-v$で接続されたコンポーネントを返す。
目標は、平均的な検索コストを最小限に抑える検索戦略を設計することである。
まず,頂点を問合せするコストが対象と無関係である場合を考える。
我々は、$O(n^4/ε^2)$時間で走る木に対する$\br{4+ε}$-approximation FPTASと、一般グラフに対する$O({\sqrt{\log n}})$-approximationを開発する。
さらに、グラフの非リーフ頂点の数によってパラメトリケートされたFPTASを与える。
硬度側では、入力が有界度または有界径のツリーである場合でも、問題はNPハードであることが証明される。
第二に、木を考慮し、$c(v, x)$を$x$、すなわち、$u \in P_{v, x}$ならば$c(u, x) \leq c(v, x)$に対して単調な非減少函数と仮定する。
最低ケースの変種に対して簡単に修正できる2ドルの近似アルゴリズムを提供する。
これは両基準に対する最初の定数係数近似アルゴリズムである。
これまでは、最悪の検索コストのみを考慮し、パラメータ化されたPTASと、パスに対する4ドルの近似を含むことが知られていた。
最後に、コスト関数がクエリされた頂点と対象の任意の関数である場合、入力木がスターである場合でも、UGCの下での定数係数近似は認められないことを示す。
関連論文リスト
- Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。
実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。
単純な2n列挙アルゴリズムを破るMVBPを提案する。
FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
論文 参考訳（メタデータ） (2024-09-27T06:23:29Z) - Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology [0.0]
我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。
解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。
MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
論文 参考訳（メタデータ） (2023-12-15T09:42:46Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。