Fugu-MT 論文翻訳(概要): Knapsack: Connectedness, Path, and Shortest-Path

論文の概要: Knapsack: Connectedness, Path, and Shortest-Path

arxiv url: http://arxiv.org/abs/2307.12547v2
Date: Fri, 5 Jan 2024 06:23:17 GMT
ステータス: 処理完了
システム内更新日: 2024-01-08 18:15:17.412537
Title: Knapsack: Connectedness, Path, and Shortest-Path
Title（参考訳）: Knapsack: 接続性、パス、最短パス
Authors: Palash Dey, Sudeshna Kolay, and Sipra Singh
Abstract要約: 特に、連結knapsack問題において、knapsack制約の大きさの最大値を持つ項目の連結部分集合を計算する必要がある。この問題は、最大次数4のグラフでもNP完全であり、スターグラフでもNP完全であることを示す。 path-knapsack や shortestpath-knapsack という問題名の下で、グラフ理論上の他のいくつかの性質について同様の結果を示す。
参考スコア（独自算出の注目度）: 4.915744683251151
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs to satisfy certain graph theoretic properties on top of knapsack constraints. In particular, we need to compute in the connected knapsack problem a connected subset of items which has maximum value subject to the size of knapsack constraint. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(\min\{s^2,d^2\})\right)$ where $tw,s,d$ are respectively treewidth of the graph, size, and target value of the knapsack. We further exhibit a $(1-\epsilon)$ factor approximation algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(n,1/\epsilon)\right)$ for every $\epsilon>0$. We show similar results for several other graph theoretic properties, namely path and shortest-path under the problem names path-knapsack and shortestpath-knapsack. Our results seems to indicate that connected-knapsack is computationally hardest followed by path-knapsack and shortestpath-knapsack.
Abstract（参考訳）: グラフ理論の制約によりナップサック問題を研究する。すなわち、knapsack の項目の集合上にグラフ構造が存在すると仮定し、この解は knapsack の制約の上にあるグラフ理論的性質を満たす必要がある。特に、コネクテッド・ナップサック問題(connected knapsack problem)において、コネクテッド・ナップサック制約の大きさに対応する最大値を持つ項目の連結部分集合を計算する必要がある。この問題は、最大次数4のグラフでもNP完全であり、スターグラフでもNP完全であることを示す。一方、時刻 $o\left(2^{tw\log tw}\cdot\text{poly}(\min\{s^2,d^2\})\right)$ where $tw,s,d$ はそれぞれグラフのツリー幅、サイズ、目標値である。さらに、$(1-\epsilon)$ factor approximation アルゴリズムを、$o\left(2^{tw\log tw}\cdot\text{poly}(n,1/\epsilon)\right)$ ごとに実行しています。 path-knapsack や shortestpath-knapsack という問題名の下で、グラフ理論上の他のいくつかの性質について同様の結果を示す。結果は,connected-knapsackが最も計算が難しいことを示し,path-knapsack と shortestpath-knapsack が続いた。

関連論文リスト

Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文参考訳（メタデータ） (2024-08-19T21:30:02Z)
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)
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文参考訳（メタデータ） (2023-06-08T14:48:48Z)
Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文参考訳（メタデータ） (2023-06-05T15:35:00Z)
The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-11T17:33:07Z)
Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文参考訳（メタデータ） (2021-11-02T05:26:10Z)
A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文参考訳（メタデータ） (2021-10-29T07:35:46Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
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)

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

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