1,720,983 research outputs found
Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to Stable Matchings
Get PDFIn this paper, we study a slightly different definition of popularity in bipartite graphs with two-sided preferences, when ties are present in the preference lists. This is motivated by the observation that if an agent is indifferent between his original partner in matching and his new partner in matching , then he may probably still prefer to stay with his original partner, as change requires effort, so he votes for in this case, instead of being indifferent.
We show that this alternative definition of popularity, which we call weak-popularity allows us to guarantee the existence of such a matching and also to find a weakly-popular matching in polynomial-time that has size at least the size of the maximum weakly popular matching. We also show that this matching is at least times the size of the maximum (weakly) stable matching, so may provide a more desirable solution than the current best (and tight under certain assumptions) -approximation for such a stable matching. We also show that unfortunately, finding a maximum size weakly popular matching is NP-hard, even with one-sided ties and that assuming some complexity theoretic assumptions, the -approximation bound is tight.
Then, we study a more general model than weak-popularity, where for each edge, we can specify independently for both endpoints the size of improvement the endpoint needs to vote in favor of a new matching . We show that even in this more general model, a so-called -popular matching always exists and that the same positive results still hold.
Finally, we define an other, stronger variant of popularity, called super-popularity, where even a weak improvement is enough to vote in favor of a new matching. We show that for this case, even the existence problem is NP-hard
Popularity and Perfectness in One-sided Matching Markets with Capacities
Get PDFWe consider many-to-one matching problems, where one side corresponds to
applicants who have preferences and the other side to houses who do not have
preferences. We consider two different types of this market: one, where the
applicants have capacities, and one where the houses do. First, we answer an
open question by Manlove and Sng (2006) (partly solved Paluch (2014) for
preferences with ties), that is, we show that deciding if a popular matching
exists in the house allocation problem, where agents have capacities is NP-hard
for previously studied versions of popularity. Then, we consider the other
version, where the houses have capacities. We study how to optimally increase
the capacities of the houses to obtain a matching satisfying multiple
optimality criteria, like popularity, Pareto-optimality and perfectness. We
consider two common optimality criteria, one aiming to minimize the sum of
capacity increases of all houses and the other aiming to minimize the maximum
capacity increase of any school. We obtain a complete picture in terms of
computational complexity and some algorithms
A Simple 1.5-Approximation Algorithm for a Wide Range of Max-SMTI Problems
Get PDFWe give a simple approximation algorithm for a common generalization of many
previously studied extensions of the maximum size stable matching problem with
ties. These generalizations include the existence of critical vertices in the
graph, amongst whom we must match as much as possible, free edges, that cannot
be blocking edges and -stabilities, which mean that for an edge to
block, the improvement should be large enough on one or both sides. We also
introduce other notions to generalize these even further, which allows our
framework to capture many existing and future applications. We show that the
edge duplicating technique allows us to treat these different types of
generalizations simultaneously, while also making the algorithm, the proofs and
the analysis much simpler and shorter than in previous approaches. In
particular, we answer an open question by Askalidis et al. (2013) about the
existence of a -approximation algorithm for the MAX-SMTI problem
with free edges. This demonstrates that this technique can grasp the underlying
essence of these problems quite well and have the potential to be able to solve
many future applications
Popular and Dominant Matchings with Uncertain, Multilayer and Aggregated Preferences
Get PDFWe study the Popular Matching problem in multiple models, where the
preferences of the agents in the instance may change or may be
unknown/uncertain. In particular, we study an Uncertainty model, where each
agent has a possible set of preferences, a Multilayer model, where there are
layers of preference profiles, a Robust model, where any agent may move some
other agents up or down some places in his preference list and an Aggregated
Preference model, where votes are summed over multiple instances with different
preferences.
We study both one-sided and two-sided preferences in bipartite graphs. In the
one-sided model, we show that all our problems can be solved in polynomial time
by utilizing the structure of popular matchings. We also obtain nice structural
results. With two-sided preferences, we show that all four above models lead to
NP-hard questions for popular matchings. By utilizing the connection between
dominant matchings and stable matchings, we show that in the robust and
uncertainty model, a certainly dominant matching in all possible prefernce
profiles can be found in polynomial-time, whereas in the multilayer and
aggregated models, the problem remains NP-hard for dominant matchings too.
We also answer an open question about -robust stable matchings
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Popular and Dominant Matchings with Uncertain and Multimodal Preferences
No full textWe study the Popular Matching (PM) problem in multiple models, where the preferences of the agents in the instance may change or may be unknown or uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preference lists, a Multilayer model, where there are layers of preference profiles, and a Robust popularity model, where any agent may move some other agents up or down some places in his preference list. Our goal is always to find a matching that is popular in any possible preference profile.We study both one-sided (only one class of the agents have preferences) and two-sided bipartite markets. In the one-sided model, we show that all our problems can be solved in polynomial time by utilizing the structure of popular matchings. We also obtain nice structural results. With two-sided preferences, we show that all three above models lead to NP-hard questions for popular matchings. By using the connection between dominant matchings and stable matchings, we show that in the robust and uncertainty models, a certainly dominant matching in all possible preference profiles can be found in polynomial time, whereas in the multilayer model, the problem remains NP-hard for dominant matchings too. We also answer an open question about d-robust stable matchings
- …
