論文の概要: Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
- arxiv url: http://arxiv.org/abs/2311.00405v2
- Date: Sat, 11 May 2024 09:46:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-15 01:02:54.930420
- 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要約: サブレスポンシブでサブコンプリートなカップルを持つ sc hrc が NP-hard であることを示す。
また、Dual Market を持つ sc hrc は、複数の同時制限の下でNPハードであることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we study the {\sc Hospitals / Residents problem with Couples} ({\sc 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 {\sc hrc} instance where the couples' preferences are sub-responsive (i.e., if one member switches to a better hospital, than 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 {\sc Stable Fixtures} problem. We also present a polynomial-time algorithm for {\sc 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 {\sc hrc} with sub-responsive and sub-complete couples is NP-hard, even with other strong restrictions. We also show that {\sc 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 {\sc 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 {\sc hrc} and provide additional evidence as to why long-standing entry-level labour markets that allow couples such as the National Resident Matching Program remain successful to this day.
- Abstract（参考訳）: 本稿では, ソリューションが安定なマッチングや, 存在しない報告であるクープルズ問題 ({\sc hrc}) について検討する。
我々は、カップルの嗜好がサブレスポンシブである(つまり、あるメンバーがより良い病院に切り替える場合、カップルが改善する)とサブコンプリート(つまり、双方のメンバーに個別に受け入れられる病院のペアは、カップルに共同で受け入れられる)のインスタンスに還元することで、ほぼ実現可能な安定なマッチング(病院の容量を少なくとも1で調整する)を見つけることができる新しい多項式時アルゴリズムを提案する。
また、双対市場であるサブレスポンシブでサブコンプリートなインスタンスで {\sc hrc} の多項式時間アルゴリズムを提案する。
また,本アルゴリズムは,グラフがループを持つ多重グラフである安定なbマッチング問題の多項式時間可解性についても示唆する。
我々はアルゴリズムをいくつかの難しい結果で補完する。
サブレスポンシブでサブコンプリートなカップルを持つ {\sc hrc} は、他の強い制約があってもNPハードであることを示す。
また、デュアルマーケットを持つ {\sc hrc} は、複数の同時制限の下でNPハードであることを示す。
最後に、$m^{1-\varepsilon}$, for any $\varepsilon>0$, where $m$ is the total length of the hospitals' preference list, if if each couple may to only one pair of hospitals。
我々の多項式時間可解性は、既知のcsc 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) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。