論文の概要: Couples can be tractable: New algorithms and hardness results for the
Hospitals / Residents problem with Couples
- arxiv url: http://arxiv.org/abs/2311.00405v1
- Date: Wed, 1 Nov 2023 09:56:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 14:08:14.875808
- Title: Couples can be tractable: New algorithms and hardness results for the
Hospitals / Residents problem with Couples
- Title(参考訳): カップルは扱いやすい: カップルの病院・住民問題に対する新しいアルゴリズムとハードネス結果
- Authors: Gergely Cs\'aji, David Manlove, Iain McBride and 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}) を考察する。
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.
また,双対市場であるサブレスポンシブ・サブコンプリート・インスタンスや,すべてのカップルが複数の可能なタイプの1つである場合の多項式時間アルゴリズムを提案する。
また,本アルゴリズムは,グラフがループを持つ多重グラフである安定なbマッチング問題の多項式時間可解性についても示唆する。
我々はアルゴリズムをいくつかの難しい結果で補完する。
サブレスポンシブかつサブ完全結合を持つ {\sc hrc} は、他の強い制限でもnp-hardである。
また、デュアルマーケットを持つ {\sc hrc} は、複数の同時制限の下でNPハードであることを示す。
最後に、任意の$\varepsilon>0$ に対して、 {\sc hrc} における最小のブロックペア数とのマッチングを見つける問題は、m$ が病院の選好リストの総長である場合、p=np の場合を除き、各カップルが1対の病院にのみ適用される場合であっても、約$m^{1-\varepsilon}$ 以内にはならないことを示した。
我々の多項式時間可解性は、既知のcsc hrcの抽出可能なインスタンスのクラスを大きく拡大し、なぜ国家居住者マッチングプログラムのようなカップルが今日まで成功し続けるのかを、長期にわたるエントリーレベルの労働市場が示している。
関連論文リスト
- Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳(メタデータ) (2023-01-19T11:36:50Z) - Resource Sharing Through Multi-Round Matchings [27.98321373077565]
1ラウンド当たりのマッチングの集合は、もし存在するなら、効率的に見つけることができることを示す。
提案アルゴリズムを合成ネットワーク上で実験的に評価し,2つの実環境 – 共有オフィススペースとマッチングコース – に適用した。
論文 参考訳(メタデータ) (2022-11-30T17:46:43Z) - A Multivariate Complexity Analysis of Qualitative Reasoning Problems [9.594432031144716]
我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。
有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。
また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$ timeで解決可能であり、その中に含まれることを示す。
論文 参考訳(メタデータ) (2022-09-30T07:29:53Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳(メタデータ) (2022-06-17T09:24:41Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳(メタデータ) (2021-06-02T12:50:56Z) - Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
P=NPがなければ、二次プログラムの局所最小値のユークリッド距離内の点を見つけるSDPは存在しないことを示す。
また、最適値が有限であるプログラムが最適解を持つか否かをテストすることはNPハードであることを示す。
最終章では,SDPの階層化に寄与する強制力の特性について紹介する。
論文 参考訳(メタデータ) (2020-08-27T14:58:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Pair-Matching: Links Prediction with Adaptive Queries [7.22341371511072]
グラフが2つのコミュニティを持つブロックモデル(SBM)に従って生成される場合、サブ線形後悔が達成可能であることを示す。
この論文は, コミュニティの数が2より多い場合に, 最適後悔に関する予想によって締めくくられる。
論文 参考訳(メタデータ) (2019-05-17T15:57:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。