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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Many important stable matching problems are known to be NP-hard, even whenstrong restrictions are placed on the input. In this paper we seek to identifystructural properties of instances of stable matching problems which will allowus to design efficient algorithms using elementary techniques. We focus on thesetting in which all agents involved in some matching problem can bepartitioned into k different types, where the type of an agent determines hisor her preferences, and agents have preferences over types (which may berefined by more detailed preferences within a single type). This situationwould arise in practice if agents form preferences solely based on some smallcollection of agents' attributes. We also consider a generalisation in whicheach agent may consider some small collection of other agents to beexceptional, and rank these in a way that is not consistent with their types;this could happen in practice if agents have prior contact with a small numberof candidates. We show that (for the case without exceptions), severalwell-studied NP-hard stable matching problems including Max SMTI (that offinding the maximum cardinality stable matching in an instance of stablemarriage with ties and incomplete lists) belong to the parameterised complexityclass FPT when parameterised by the number of different types of agents neededto describe the instance. For Max SMTI this tractability result can be extendedto the setting in which each agent promotes at most one `exceptional' candidateto the top of his/her list (when preferences within types are not refined), butthe problem remains NP-hard if preference lists can contain two or moreexceptions and the exceptional candidates can be placed anywhere in thepreference lists, even if the number of types is bounded by a constant.

Solving Hard Stable Matching Problems Involving Groups of Similar Agents