Search Results

We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching k-stable if no other matching exists that is more beneficial to at ...

A recently introduced restricted variant of the multidimensional stable roommates problem is the roommate diversity problem: each agent belongs to one of two types (e.g., red and blue), and the agents' preferences over the rooms solely depend on ...

• Popular partitioning on RDP with room size 2 can be computed in polynomial time.
• Mixed popular partitioning is always guaranteed to exist in any RDP instance.
• Deciding if a (strictly) popular partitioning exists is co-NP-hard.
• ...

Gale and Shapley’s stability criterion enjoys a rich mathematical structure, which propelled its application in various settings. Although immensely popular, the approach by Gale and Shapley cannot encompass all the different features that arise ...

The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of ...

This paper provides a solution to mitigate mistrust that arises from untransparency in a multi-stakeholder environment. This work is related to a kind of verifiable computation. When considering the multi-stakeholder environment, not only the ...${}^{\mathrm{}}$

Stable matching is an important problem that receives attention from researchers in several fields. In the problem setting, there are two sets with the same number of members. Each member has its matching preference. The goal is to find a one-to-...

We focus on an online 2-stage problem, motivated by the following situation: consider a system where students shall be assigned to universities. There is a first round where some students apply, and a first (stable) matching M 1 has to be ...

In this paper, we consider a matching in a bipartite graph where each vertex has a preference over the edges incident to it. Especially, we consider the case where a preference of a vertex is defined based on comparisons of any two ...

• We consider a bipartite graph with pairwise preferences.
• We consider a Pareto ...

An instance I of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in I is the exchange of two consecutive vertices in a preference list. A swap can be viewed ...

We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We ...

The Student-Project Allocation problem with lecturer preferences over Students with Ties (SPA-ST) is to find a stable matching of students and projects to satisfy the constraints on student preferences over projects, lecturer preferences over ...

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as ...

We provide a linear description of the unconstrained stable allocations problem by proving that the corresponding polytope is affinely congruent to the order polytope of a partially ordered set. The same holds for stable matchings ...

The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of ...

In this paper we study stable multicommodity flows, stable hypergraph matchings and some related problems, like the Hospital-Resident-Couple (hrc) problem. We give a simpler proof of the existence of a stable multicommodity flow by ...

• Stable fractional solutions are PPAD-hard to find in HRC and Stable Family Problem.

To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties, Proc. STACS 2022, pp. 31:1–31:20] studied the ...

Multi-label active learning (MLAL) reduces the cost of manual annotation for multi-label problems by selecting high-quality unlabeled data. Existing MLAL methods usually perform a one-way selection by considering the examples’ ...

Intelligent reflecting surfaces (IRSs) are anticipated to provide reconfigurable propagation environment for next generation communication systems. In this paper, we investigate a downlink IRS-aided multi-carrier (MC) non-orthogonal ...

The sharing economy has promoted the rapid development of the global economy, the stable matching plays a vital role in resource sharing. However, the large-scale platform increases the difficulties of stable matching, like low ...

• The two-stage mechanism is designed to realize stable efficient matching in large-scale sharing platform.

The Student-Project Allocation problem with lecturer preferences over Students (spa-s) involves assigning students to projects based on student preferences over projects, lecturer preferences over students, and the maximum number of students that ...