Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem

Author Vijay K. Garg



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.52.pdf
  • Filesize: 390 kB
  • 3 pages

Document Identifiers

Author Details

Vijay K. Garg

Cite AsGet 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.
Keywords
  • Stable Matching
  • Linear Predicates
  • Distributive Lattices

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Craig M Chase and Vijay K Garg. Detection of global predicates: Techniques and their limitations. Distributed Computing, 11(4):191-201, 1998. Google Scholar
  2. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  3. 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.
  4. Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  5. Neeraj Mittal and Vijay K Garg. Computation slicing: Techniques and theory. In International Symposium on Distributed Computing, pages 78-92. Springer, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail