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

作者：Kijima Shuji^*; Nemoto Toshio

来源：Mathematics of Operations Research, 2012, 37(2): 356-371.

DOI：10.1287/moor.1110.0526

• randomized algorithms
• stable marriage
• order ideals
• #P-hard
• randomized approximation scheme (FPRAS)

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 p is an element of P 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 %26quot;fairness%26quot; of matchings in a stable marriage problem. Cheng [Cheng, C. T. 2010. Understanding the generalized median stable matchings. Algorithmica 58(1) 34-51] showed that finding the ith LI is #P-hard when i = Theta(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 = Theta(N-1/c), where c is an arbitrary constant at least one. Meanwhile, we present a polynomial time exact algorithm when i = O((log N)(c%26apos;)), where c%26apos; 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.

• 出版日期2012-5