Publication:
Rank-maximal matchings – structure and algorithms

Simple item page
cris.author.scopus-author-id56494647900
cris.author.scopus-author-id25522226600
cris.author.scopus-author-id27467703700
cris.virtual.author-orcid#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtual.author-orcid0000-0003-0290-4444
cris.virtual.author-orcid#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtual.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtual.departmentIndian Institute of Technology, Madras
cris.virtual.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.author-orcid#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.author-orcid6ed3be9b-3c38-4ded-afeb-ddf18983bc07
cris.virtualsource.author-orcid#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.department6ed3be9b-3c38-4ded-afeb-ddf18983bc07
cris.virtualsource.department#PLACEHOLDER_PARENT_METADATA_VALUE#
dc.contributor.authorGhosal, Pratik
dc.contributor.authorMeghana Nasre
dc.contributor.authorNimbhorkar, Prajakta
dc.date.accessioned2023-09-20T05:24:53Z
dc.date.available2023-09-20T05:24:53Z
dc.date.issued01-01-2014
dc.description.abstractLet (Formula presented.) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem.
dc.identifier.doi10.1007/978-3-319-13075-0_47
dc.identifier.issn3029743
dc.identifier.scopus2-s2.0-84921821344
dc.identifier.urihttps://apicris.irins.org/handle/IITM2023/43798
dc.relation.ispartofseriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.titleRank-maximal matchings – structure and algorithms
dc.typeBook Series
dspace.entity.typePublication
oaire.citation.endPage605
oaire.citation.startPage593
oaire.citation.volume8889
oairecerif.author.affiliation#PLACEHOLDER_PARENT_METADATA_VALUE#
oairecerif.author.affiliationIndian Institute of Technology, Madras
oairecerif.author.affiliation#PLACEHOLDER_PARENT_METADATA_VALUE#
person.affiliation.cityChennai
person.affiliation.cityKelambakkam
person.affiliation.cityWroclaw
person.affiliation.id60025757
person.affiliation.id60019021
person.affiliation.id60016147
person.affiliation.nameIndian Institute of Technology Madras
person.affiliation.nameChennai Mathematical Institute
person.affiliation.nameUniversity of Wroclaw
Files
Collections
Publication7