English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 noneexists. We present a novel polynomial-time algorithm that can find anear-feasible stable matching (adjusting the hospitals' capacities by at most1) 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 alsoimproves) and sub-complete (i.e., each pair of hospitals that are individuallyacceptable to both members are jointly acceptable for the couple) by reducingit to an instance of the {\sc Stable Fixtures} problem. We also present apolynomial-time algorithm for {\sc hrc} in a sub-responsive, sub-completeinstance that is a Dual Market, or where all couples are one of severalpossible types. We show that our algorithm also implies the polynomial-timesolvability of a stable b-matching problem, where the underlying graph is amultigraph with loops.  We complement our algorithms with several hardness results. We show that {\schrc} with sub-responsive and sub-complete couples is NP-hard, even with otherstrong restrictions. We also show that {\sc hrc} with a Dual Market is NP-hardunder several simultaneous restrictions. Finally, we show that the problem offinding a matching with the minimum number of blocking pairs in {\sc hrc} isnot approximable within $m^{1-\varepsilon}$, for any $\varepsilon>0$, where $m$is the total length of the hospitals' preference lists, unless P=NP, even ifeach couple applies to only one pair of hospitals. Our polynomial-timesolvability results greatly expand the class of known tractable instances of{\sc hrc} and provide additional evidence as to why long-standing entry-levellabour markets that allow couples such as the National Resident MatchingProgram remain successful to this day.

Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples