Popular Half-Integral Matchings

Kavitha, Telikepalli

doi:10.4230/LIPIcs.ICALP.2016.22

File

LIPIcs.ICALP.2016.22.pdf

Filesize: 0.49 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ICALP.2016.22
URN: urn:nbn:de:0030-drops-63011

Author Details

Telikepalli Kavitha

Cite AsGet BibTex

Telikepalli Kavitha. Popular Half-Integral Matchings. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.22

Abstract

In an instance G = (A union B, E) of the stable marriage problem with strict and possibly incomplete preference lists, a matching M is popular if there is no matching M0 where the vertices that prefer M' to M outnumber those that prefer M to M'. All stable matchings are popular and there is a simple linear time algorithm to compute a maximum-size popular matching. More generally, what we seek is a min-cost popular matching where we assume there is a cost function c : E -> Q. However there is no polynomial time algorithm currently known for solving this problem. Here we consider the following generalization of a popular matching called a popular half-integral matching: this is a fractional matching ~x = (M_1 + M_2)/2, where M1 and M2 are the 0-1 edge incidence vectors of matchings in G, such that ~x satisfies popularity constraints. We show that every popular half-integral matching is equivalent to a stable matching in a larger graph G^*. This allows us to solve the min-cost popular half-integral matching problem in polynomial time.

Keywords

bipartite graphs
stable matchings
fractional matchings
polytopes

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007.
P. Biró, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In Proceedings of 7th International Conference on Algorithms and Complexity (CIAC), pages 97-108, 2010.
Á. Cseh, C.-C. Huang, and T. Kavitha. Popular matchings with two-sided preferences and one-sided ties. In Proceedings of 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 367-379, 2015.
Á. Cseh and T. Kavitha. Popular edges and dominant matchings. To appear in the Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2016.
T. Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45:233-284, 1992.
T. Feder. Network flow and 2-satisfiability. Algorithmica, 11(3):291-319, 1994.
D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11:223-232, 1985.
P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Sciences, 20:166-173, 1975.
C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013.
R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 38(3):532-543, 1987.
T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014.
T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412:2679-2690, 2011.
U. Rothblum. Characterization of stable matchings as extreme points of a polytope. Mathematical Programming, 54:57-67, 1992.
C.-P. Teo and J. Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874-891, 1998.
J. H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8(3):147-153, 1989.