論文の概要: Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds

• arxiv url: http://arxiv.org/abs/2512.24037v1
• Date: Tue, 30 Dec 2025 07:23:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-01 23:27:28.309384
• Title: Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
• Title（参考訳）: Kidney Exchange: より高速なパラメータ化アルゴリズムとよりタイトな下界
• Authors: Aritra Banik, Sujoy Bhore, Palash Dey, Abhishek Sahu,
• Abstract要約: 我々は,Ostarleft((4e)tright)approx Ostarleft(10.88tright)$で時間的に動作する決定論的FPTアルゴリズムを提案する。 ここでの自然な疑問は、腎臓交換問題は、基礎となる非方向グラフのパス幅によってパラメータ化されたFPTアルゴリズムを許容するかどうかである。
• 参考スコア（独自算出の注目度）: 2.766980867006755
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to infrastructure and legal constraints, kidney exchange can only be performed in small cycles in practice. In reality, there are also some altruistic donors who do not have any paired patients. This allows us to also perform kidney exchange along paths that start from some altruistic donor. Unfortunately, the computational task is NP-complete. To overcome this computational barrier, an important line of research focuses on designing faster algorithms, both exact and using the framework of parameterized complexity. The standard parameter for the kidney exchange problem is the number $t$ of patients that receive a healthy kidney. The current fastest known deterministic FPT algorithm for this problem, parameterized by $t$, is $O^\star\left(14^t\right)$. In this work, we improve this by presenting a deterministic FPT algorithm that runs in time $O^\star\left((4e)^t\right)\approx O^\star\left(10.88^t\right)$. This problem is also known to be W[1]-hard parameterized by the treewidth of the underlying undirected graph. A natural question here is whether the kidney exchange problem admits an FPT algorithm parameterized by the pathwidth of the underlying undirected graph. We answer this negatively in this paper by proving that this problem is W[1]-hard parameterized by the pathwidth of the underlying undirected graph. We also present some parameterized intractability results improving the current understanding of the problem under the framework of parameterized complexity.
• Abstract（参考訳）: 腎臓交換機構は、他の方法では相容れない多くの患者とドナーのペアが、サイクルに沿って腎臓を交換することを可能にする。 しかし、インフラと法的な制約のため、腎臓交換は実際には小さなサイクルでしか行えない。 実際には、ペアの患者がいない利他的なドナーもいる。 これにより、一部の利他的なドナーから始まる経路に沿って腎臓交換を行うこともできます。 残念ながら、計算タスクはNP完全である。 この計算障壁を克服するために、重要な研究は、パラメータ化複雑性のフレームワークの正確性と使用の両方において、より高速なアルゴリズムの設計に焦点を当てている。 腎臓交換問題の標準パラメータは、健康な腎臓を受け取った患者の数$t$である。 現在知られているこの問題の最も高速な決定論的FPTアルゴリズムは$t$でパラメータ化され、$O^\star\left(14^t\right)$である。 本研究では,O^\star\left((4e)^t\right)\approx O^\star\left(10.88^t\right)$における決定論的FPTアルゴリズムを提案する。 この問題は、下層の無向グラフのツリー幅によってW[1]-ハードパラメータ化されることも知られている。 ここでの自然な疑問は、腎臓交換問題は、基礎となる非方向グラフのパス幅によってパラメータ化されたFPTアルゴリズムを許容するかどうかである。 この問題は、基礎となる非方向グラフのパス幅によってパラメータ化され、W[1]-ハードであることが証明された。 また,パラメータ化複雑性の枠組みの下で問題に対する現在の理解を改善するために,パラメータ化インタラクタビリティの結果も提示する。

関連論文リスト

• Improving Decision Trees through the Lens of Parameterized Local Search [9.426097667758627]
  本研究では,これらの操作の1種類の固定数を実行することにより,分類誤差の最小化について検討する。 本稿では,本アルゴリズムの概念実証実装と実験結果について報告する。
  論文  参考訳（メタデータ） (2025-10-14T17:06:13Z)
• Systematic Parameter Decision in Approximate Model Counting [15.68459774228961]
  本稿ではハッシュベースの近似モデルカウントアルゴリズム$mathsfApproxMC$の内部パラメータを決定する新しい手法を提案する。 削減後、結果の最適化問題は極めて単純な形で行われ、基本的な探索アルゴリズムが利用可能となる。 実験の結果,最新の$mathsfApproxMC$のパラメータを1.6～2.4で改善した。
  論文  参考訳（メタデータ） (2025-04-08T09:58:41Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter [12.006511319607473]
  本稿では,Plug-Play(PGD)アルゴリズムの収束性について述べる。 最近の研究は、証明(DRS)による収束を探求している。 まず、新しい収束証明を提供する。 正規化にいかなる制限も課さないDSS。 第2に、画像復元の精度を高めるPGDの緩和版について検討する。
  論文  参考訳（メタデータ） (2023-11-02T13:18:39Z)
• Solving the Kidney-Exchange Problem via Graph Neural Networks with No Supervision [1.469597968606607]
  本稿では,KidneyExchange Problem (KEP) を解くための学習に基づく新しいアプローチを提案する。 この問題は、腎臓提供者のプールと腎臓提供者を待っている患者が与えられた場合、移植の量と品質を最適化するために、最適に寄付のセットを選択します。 提案手法は2つの主要なステップから構成される: 1つは教師無しで訓練されたグラフニューラルネットワーク(GNN)、2つ目はGNNの出力を使って経路やサイクルを見つける決定論的非学習探索である。
  論文  参考訳（メタデータ） (2023-04-19T21:25:34Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Adapting a Kidney Exchange Algorithm to Align with Human Values [59.395925461012126]
  腎臓交換における個人プロファイルの重み付けをエンドツーエンドに推定する手法を提案する。 これらの重量を腎臓交換市場浄化アルゴリズムでどのように使うかを示す。
  論文  参考訳（メタデータ） (2020-05-19T21:00:29Z)

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

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