LIPIcs.DISC.2017.52.pdf
- Filesize: 390 kB
- 3 pages
Document
Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
Author
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get BibTex
Vijay K. Garg. Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.52
Abstract
We show that many techniques developed in the context of predicate detection are applicable to the stable marriage problem. The standard Gale-Shapley algorithm can be derived as a special case of detecting linear predicates. We also show that techniques in computation slicing can be used to represent the set of all constrained stable matchings.
Subject Classification
Keywords
- Stable Matching
- Linear Predicates
- Distributive Lattices
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Craig M Chase and Vijay K Garg. Detection of global predicates: Techniques and their limitations. Distributed Computing, 11(4):191-201, 1998.
-
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962.
- Vijay K. Garg. Applying predicate detection to the stable marriage problem. Technical Report TR-PDS-2017-001, The University of Texas at Austin, May 2017. URL: http://users.ece.utexas.edu/~garg/TechReports/2017/TR-PDS-2017-001.pdf.
-
Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989.
-
Neeraj Mittal and Vijay K Garg. Computation slicing: Techniques and theory. In International Symposium on Distributed Computing, pages 78-92. Springer, 2001.