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

Published Online:https://doi.org/10.1287/moor.1110.0526

This study is concerned with finding a level ideal (LI) of a partially ordered set (poset). Given a finite poset P, the level of each element pP is defined as the number of ideals that do not include p, then the problem is to find the ith LI–the ideal consisting of elements whose levels are less than a given integer i. The concept of a level ideal is naturally derived from the generalized median stable matchings, introduced by Teo and Sethuraman [Teo, C. P., J. Sethuraman. 1998. The geometry of fractional stable matchings and its applications. Math. Oper. Res.23(4) 874–891] in the context of “fairness” of matchings in a stable marriage problem. Cheng [Cheng, C. T. 2010. Understanding the generalized median stable matchings. Algorithmica58(1) 34–51] showed that finding the ith LI is #P-hard when i = Θ(N), where N is the total number of ideals of P. This paper shows that finding the ith LI is #P-hard even if i = Θ(N1/c), where c is an arbitrary constant at least one. Meanwhile, we present a polynomial time exact algorithm when i = O((log N)c′), where c′ is an arbitrary positive constant. We also devise two randomized approximation schemes for the ideals of a poset, by using an oracle of an almost-uniform sampler.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.