論文の概要: 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: 接続性、パス、最短パス
• 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 が続いた。

関連論文リスト

• Quantum algorithms for path and cycle containment problems [0.22940141855172036]
  本稿では,隣接行列モデルにおけるパスとサイクルを含む問題の変種について考察する。 経路包含問題のいくつかは、線形数のクエリを使って解決でき、他の全ては互いに等価である。 クエリ複雑性を$widetildeO(n3/2-_k)$, $_k in (c-k)$, $c = sqrt3+sqrt17/2 で実現する新しい量子ウォークベースのアルゴリズムを証明した。
  論文  参考訳（メタデータ） (2026-05-09T15:55:07Z)
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。 驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
  論文  参考訳（メタデータ） (2026-04-17T14:47:52Z)
• Average Case Graph Searching in Non-Uniform Cost Models [0.0]
  目標は、平均的な検索コストを最小限に抑える検索戦略を設計することである。 木を考慮し、$c(v, x)$ を単調な非減少関数と仮定する。 これは両基準に対する最初の定数係数近似アルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-18T16:54:24Z)
• 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)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。 古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。 我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
  論文  参考訳（メタデータ） (2023-07-24T02:50:34Z)
• 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)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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)

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

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