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

Two-sided popular matchings in bipartite graphs are a well-knowngeneralization of stable matchings in the marriage setting, and they areespecially relevant when preference lists are incomplete. In this case, thecardinality of a stable matching can be as small as half the size of a maximummatching. Popular matchings allow for assignments of larger size while stillguaranteeing a certain fairness condition. In fact, stable matchings arepopular matchings of minimum size, and a maximum size popular matching can beas large as twice the size of a(ny) stable matching in a given instance. Thestructure of popular matchings seems to be more complex, and currently lessunderstood, than that of stable matchings. In this paper, we focus on threeoptimization problems related to popular matchings. First, we give a granularanalysis of the complexity of popular matching with forbidden and forcedelements problems, thus complementing results from [Cseh and Kavitha, 2016]. Inparticular, we show that deciding whether there exists a popular matching with(or without) two given edges is NP-Hard. This implies that finding a popularmatching of maximum (resp. minimum) weight is NP-Hard and, even if all weightsare nonnegative, inapproximable up to a factor 1/2 (resp. up to any factor). Adecomposition theorem from [Cseh and Kavitha, 2016] can be employed to give a1/2 approximation to the maximum weighted popular matching problem withnonnegative weights, thus completely settling the complexity of those problems.

Two-sided popular matchings in bipartite graphs with forbidden/forced elements and weights