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 the stable marriage and roommates problems, a set of agents is given, eachof them having a strictly ordered preference list over some or all of the otheragents. A matching is a set of disjoint pairs of mutually accepted agents. Ifany two agents mutually prefer each other to their partner, then they block thematching, otherwise, the matching is said to be stable. In this paper weinvestigate the complexity of finding a solution satisfying additionalconstraints on restricted pairs of agents. Restricted pairs can be eitherforced or forbidden. A stable solution must contain all of the forced pairs,while it must contain none of the forbidden pairs.  Dias et al. gave a polynomial-time algorithm to decide whether such asolution exists in the presence of restricted edges. If the answer is no, onemight look for a solution close to optimal. Since optimality in this contextmeans that the matching is stable and satisfies all constraints on restrictedpairs, there are two ways of relaxing the constraints by permitting a solutionto: (1) be blocked by some pairs (as few as possible), or (2) violate someconstraints on restricted pairs (again as few as possible).  Our main theorems prove that for the (bipartite) stable marriage problem,case (1) leads to NP-hardness and inapproximability results, whilst case (2)can be solved in polynomial time. For the non-bipartite stable roommatesinstances, case (2) yields an NP-hard problem. In the case of NP-hard problems,we also discuss polynomially solvable special cases, arising from restrictionson the lengths of the preference lists, or upper bounds on the numbers ofrestricted pairs.

Stable marriage and roommates problems with restricted edges: complexity and approximability