On Randomized Approximation for Finding a Level Ideal of a Poset and the Generalized Median Stable Matchings

References

• Bhatnagar N., Greenberg S., Randall D., Teng S.-H. Sampling stable marriages: Why the spouse-swapping won't work. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2008) (2008) San Francisco:1223–1232Google Scholar
• Blair C. Every finite distributive lattice is a set of stable matchings. J. Combin. Theory A (1984) 37(3):353–356Crossref, Google Scholar
• Cheng C. T. Understanding the generalized median stable matchings. Algorithmica (2010) 58(1):34–51Crossref, Google Scholar
• Davey B. A., Priestley H. A.Introduction to Lattices and Order (2002) 2nd ed.(Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Dubhashi D. P., Mehlhorn K., Rajan D., Thiel C. Searching, sorting, and randomised algorithms for central elements and ideal counting in posets. Lecture Notes Comput. Sci. (1993) 761:436–443Crossref, Google Scholar
• Gale D., Shapley L. S. College admissions and the stability of marriage. Amer. Math. Monthly (1962) 69(1):9–15Crossref, Google Scholar
• Gusfield D., Irving R. W.The Stable Marriage Problem, Structure and Algorithms (1989) (MIT Press, Cambridge, MA) Google Scholar
• Irving R. W., Leather P. The complexity of counting stable marriages. SIAM J. Comput. (1986) 15(3):655–667Crossref, Google Scholar
• Jerrum M.Counting, Sampling and Integrating: Algorithms and Complexity (2003) (Birkhauser Verlag, Basel, Switzerland) Lectures in Mathematics, ETH ZürichCrossref, Google Scholar
• Kijima S., Nemoto T. Finding a level ideal of a poset. Proc. 15th Annual Internat. Conf. Comput. Combinatorics (2009) (Springer-Verlag, Berlin) 317–327Crossref, Google Scholar
• Klaus B., Klijn F. Median stable matching for college admission. Internat. J. Game Theory (2006) 34(1):1–11Crossref, Google Scholar
• Klaus B., Klijn F. Smith and Rawls share a room: Stability and medians. Soc. Choice Welfare (2010) 35(4):647–667Crossref, Google Scholar
• Knuth D.Stable Marriage and Its Relation to Other Combinatorial Problems (1991) (American Mathematical Society, Providence, RI) Google Scholar
• Nemoto T. Some remarks on the median stable marriage problem. Proc. 17th Internat. Sympos. Math. Programming (2000) AtlantaGoogle Scholar
• Propp J., Wilson D. B. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms (1996) 9(1–2):223–252Crossref, Google Scholar
• Provan J. S., Ball M. O. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. (1983) 12(4):777–788Crossref, Google Scholar
• Roth A. E., Sotomayor M. A. O.Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (1990) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Schwarz M., Yenmez M. B. Median stable matching for markets with wages. J. Econom. Theory (2011) 146(2):619–637Crossref, Google Scholar
• Sethuraman J., Teo C. P., Qian L. Many-to-one stable matching: Geometry and fairness. Math. Oper. Res. (2006) 31(3):581–596Link, Google Scholar
• Squire M. B. Enumerating the ideals of a poset. (1995) . Preprint, North Carolina State University, RaleighGoogle Scholar
• Steiner G. An algorithm for generating the ideals of a partial order. Oper. Res. Lett. (1986) 5(6):317–320Crossref, Google Scholar
• Steiner G. On the complexity of dynamic programming for sequencing problems with precedence constraints. Ann. Oper. Res. (1990) 26(1):103–123Crossref, Google Scholar
• Teo C. P., Sethuraman J. The geometry of fractional stable matchings and its applications. Math. Oper. Res. (1998) 23(4):874–891Link, Google Scholar