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

This paper deals with a complete bipartite matching problem with theobjective of finding an optimal matching that maximizes a certain genericpredefined utility function on the set of all matchings. After proving theNP-hardness of the problem using reduction from the 3-SAT problem, we propose arandomized algorithm based on Markov Chain Monte Carlo (MCMC) technique forsolving this. We sample from Gibb's distribution and construct a reversiblepositive recurrent discrete time Markov chain (DTMC) that has the steady statedistribution same as the Gibb's distribution. In one of our key contributions,we show that the constructed chain is `rapid mixing', i.e., the convergencetime to reach within a specified distance to the desired distribution ispolynomial in the problem size. The rapid mixing property is established byobtaining a lower bound on the conductance of the DTMC graph and this result isof independent interest.

Rapidly Mixing Markov Chain Monte Carlo Technique for Matching Problems with Global Utility Function