NC Algorithms for Popular Matchings in One-Sided Preference Systems and Related Problems

October 23, 2019 Β· Declared Dead Β· πŸ› IEEE International Parallel and Distributed Processing Symposium

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Changyong Hu, Vijay K. Garg arXiv ID 1910.13386 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DC Citations 1 Venue IEEE International Parallel and Distributed Processing Symposium Last Checked 4 months ago
Abstract
The popular matching problem is of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in the order of preference, possibly with ties. A matching M is popular if there is no other matching M' such that more applicants prefer M' to M. We give the first NC algorithm to solve the popular matching problem without ties. We also give an NC algorithm that solves the maximum-cardinality popular matching problem. No NC or RNC algorithms were known for the matching problem in preference systems prior to this work. Moreover, we give an NC algorithm for a weaker version of the stable matching problem, that is, the problem of finding the "next" stable matching given a stable matching.
Community shame:
Not yet rated
πŸ“„ View on arXiv 🌐 View on ar5iv πŸ“‘ PDF πŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted