Weighted Random Sampling
- PDF / 218,336 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 95 Downloads / 203 Views
W
Weighted Random Sampling
The preference lists are said to be strictly ordered if applicants are never indifferent between two items, otherwise the preference lists are said to contain ties. Let M and M 0 be two matchings. An applicant x prefers M over M 0 if x prefers the item he/she gets in M over the item he/she gets in M 0 . A matching M is more popular than M 0 if the applicants that prefer M over M 0 outweigh those that prefer M 0 over M. Finally, a matching M is weighted popular if there is no matching M 0 more popular than M. In the weighted popular matching problem it is necessary to determine if a given instance admits a popular matching, and if so, to produce one. In the maximum weighted popular matching problem it is necessary to find a popular matching of maximum cardinality, provided one exists. Abraham et al. [2] gave the first polynomial time algorithms for the special case of these problems where the weights are uniform. Later, Mestre [8] introduced the weighted variant and developed polynomial time algorithms for it. Key Results Theorem 1 The weighted popular matching and maximum weighted popular matching problems on instances with strictly ordered preferences can be solved in O(jXj + jEj) time. Theorem 2 The weighted popular matching and maximum weighted popular matching problems on instances p with arbitrary preferences can be solved in O(minfk jXj; jXjgjEj) time. Both results rely on an alternative easy-to-compute characterization of weighted popular matchings called wellformed matchings. It can be shown that every popular matching is well-formed. While in unweighted instances every well-formed matching is popular [2], in weighted instances there may be well-formed matchings that are not popular. These non-popular well-formed matchings can be weeded out by pruning certain bad edges that cannot be part of any popular matching. In other words, the instance can be pruned so that a matching is popular if and only if it is well-formed and is contained in the pruned instance [8]. Applications Many real-life problems can be modeled using one-sided preferences. For example, the assignment of graduates to training positions [5], families to government-subsidized housing [10], students to projects [9], and Internet rental
markets [1] such as Netflix where subscribers are assigned DVDs. Furthermore, the weighted framework allows one to model the naturally occurring situation in which some subset of users has priority over the rest. For example, an Internet rental site may offer a “premium” subscription plan and promise priority over “regular” subscribers. Cross References Ranked Matching Stable Marriage Recommended Reading 1. Abraham, D.J., Chen, N., Kumar, V., Mirrokni, V.: Assignment problems in rental markets. In: Proceedings of the 2nd Workshop on Internet and Network Economics, Patras, December 15–17 2006 2. Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 424–432 (2005) 3. Abraham, D
Data Loading...
