論文の概要: Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
- arxiv url: http://arxiv.org/abs/2311.00405v3
- Date: Wed, 25 Sep 2024 08:23:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 09:50:02.507792
- Title: Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
- Title（参考訳）: 夫婦の引き抜きが可能:病院・居住者問題に対する新しいアルゴリズムと難易度
- Authors: Gergely Csáji, David Manlove, Iain McBride, James Trimble,
- Abstract要約: 本研究は,ソリューションが安定したマッチングや,存在しない報告であるHRCを用いて,病院・居住者の問題を研究するものである。
ほぼ可能な安定マッチングを見つけることができる新しい時間アルゴリズムを提案する。
また,本アルゴリズムは,グラフがループを持つ多重グラフである安定なbマッチング問題の可解性も示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the Hospitals / Residents problem with Couples (HRC), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time algorithm that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) in an HRC instance where the couples' preferences are sub-responsive (i.e., if one member switches to a better hospital, then the couple also improves) and sub-complete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing it to an instance of the Stable Fixtures problem. We also present a polynomial-time algorithm for HRC in a sub-responsive, sub-complete instance that is a Dual Market, or where all couples are one of several possible types. We show that our algorithm also implies the polynomial-time solvability of a stable b-matching problem, where the underlying graph is a multigraph with loops. We complement our algorithms with several hardness results. We show that HRC with sub-responsive and sub-complete couples is NP-hard, even with other strong restrictions. We also show that HRC with a Dual Market is NP-hard under several simultaneous restrictions. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in HRC is not approximable within $m^{1-\varepsilon}$, for any $\varepsilon>0$, where $m$ is the total length of the hospitals' preference lists, unless P=NP, even if each couple applies to only one pair of hospitals. Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC and provide a useful tool for designing better and more efficient mechanisms in the future.
- Abstract（参考訳）: 本稿では,ソリューションが安定したマッチングや,存在しないレポートであるHRCを用いて,病院・居住者問題について検討する。
本研究は,カップルの嗜好がサブレスポンシブであるHRCインスタンスにおいて,ほぼ実現可能な安定なマッチング(少なくとも病院の容量を最大1で調整する)とサブコンプリート(各会員がより良い病院に切り替える場合,カップルも改善する)を実現するための新しい多項式時間アルゴリズムを提案する。
また、サブレスポンシブでサブコンプリートなインスタンスがデュアルマーケットである場合や、全てのカップルがいくつかの可能なタイプの1つである場合において、HRCの多項式時間アルゴリズムを提案する。
また,本アルゴリズムは,グラフがループを持つ多重グラフである安定なbマッチング問題の多項式時間可解性についても示唆する。
我々はアルゴリズムをいくつかの難しい結果で補完する。
サブレスポンシブカップルとサブコンプリートカップルのHRCは,他の強い制約を伴ってもNPハードであることを示す。
また、複数の同時制限の下で、デュアルマーケットを持つHRCがNPハードであることも示している。
最後に,HRCにおけるブロックペア数の最小値とのマッチングを求める問題は,各カップルが1組の病院にのみ適用される場合を除き,病院の選好リストの総長が$m$である場合,$m^{1-\varepsilon}$に対して$m^{1-\varepsilon}$で近似できないことを示す。
多項式時間可解性は, HRCの既知の抽出可能なインスタンスのクラスを大きく拡張し, 将来, より効率的かつ優れた機構を設計するための有用なツールを提供する。
関連論文リスト
- Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。
これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
論文 参考訳（メタデータ） (2024-09-19T21:40:57Z) - Unlocking the Potential of Operations Research for Multi-Graph Matching [14.3836693915104]
マルチグラフマッチングはコンピュータビジョンにおいて、例えば画像や形状のマッチングにおいて中心的な役割を果たす。
我々はMDAPのよく知られた近似アルゴリズムを不完全な多重グラフマッチングに転送する。
私たちのアルゴリズムは、2分以内でそれぞれ500以上のキーポイントを持つ29の画像と一致します。
論文 参考訳（メタデータ） (2024-06-26T09:58:05Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Manifold Proximal Point Algorithms for Dual Principal Component Pursuit
and Orthogonal Dictionary Learning [32.87704663543739]
様々な機械学習アプリケーションで発生する球面上の線形写像を最大化する問題を考える。
球面をスティーフェル行列に置き換える問題に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-05T17:40:03Z) - Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation [19.660527989370646]
我々は、その最適値に対する下界を自然に定義する緩和の族を提案する。
この族は常にゆるやかな緩和を含んでおり、我々はそれを見つけることができるアルゴリズムを与え、したがって、最初の非緩和NP-ハード問題を解く。
緩和を考えると、元の問題を2つの非重複部分(LP-tight 部分と難しい部分)に分解する。
論文 参考訳（メタデータ） (2020-04-14T09:10:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。