caa a22 4500 445805285 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9434-9 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9434-9 Bounded Unpopularity Matchings [Elektronische Daten] [Chien-Chung Huang, Telikepalli Kavitha, Dimitrios Michail, Meghana Nasre] We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M′ such that more people prefer M′ to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied by Abraham et al. (SIAM J. Comput. 37(4):1030-1045, 2007). If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity—unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have u(M)≥2 for all matchings M in G. Here we show that a matching M that achieves u(M)=2 can be computed in $O(m\sqrt{n})$ time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H=H 2,H 3, ,H k such that if H k admits a matching that matches all people, then we can compute in $O(km\sqrt{n})$ time a matching M such that u(M)≤k−1 and $g(M)\le n(1-\frac{2}{k})$. Simulation results suggest that our algorithm finds a matching with low unpopularity in random instances. Springer Science+Business Media, LLC, 2010 Matching with preferences nationallicence Popularity nationallicence Approximation algorithms nationallicence Huang Chien-Chung Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Kavitha Telikepalli Indian Institute of Science, Bangalore, India aut Michail Dimitrios Department of Informatics and Telematics, Harokopion University of Athens, Athens, Greece aut Nasre Meghana Indian Institute of Science, Bangalore, India aut Algorithmica Springer-Verlag 61/3(2011-11-01), 738-757 0178-4617 61:3<738 2011 61 453 https://doi.org/10.1007/s00453-010-9434-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9434-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Huang Chien-Chung Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Kavitha Telikepalli Indian Institute of Science, Bangalore, India aut NATIONALLICENCE 700 1- Michail Dimitrios Department of Informatics and Telematics, Harokopion University of Athens, Athens, Greece aut NATIONALLICENCE 700 1- Nasre Meghana Indian Institute of Science, Bangalore, India aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 738-757 0178-4617 61:3<738 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer