Search

We consider the problem of finding a popular matching in the Weighted Capacitated\ud House Allocation problem (WCHA). An instance of WCHA involves a set of agents\ud and a set of houses. Each agent has a positive weight indicating his priority, and a\ud preference list in which a subset of houses are ranked in strict order. Each house has\ud a capacity that indicates the maximum number of agents who could be matched to\ud it. A matching M of agents to houses is popular if there is no other matching M′\ud such that the total weight of the agents who prefer their allocation in M′\ud to that in\ud M exceeds the total weight of the agents who prefer their allocation in M to that in\ud M′\ud . Here, we give an O(\ud √\ud Cn1 + m) algorithm to determine if an instance of WCHA\ud admits a popular matching, and if so, to find a largest such matching, where C is the\ud total capacity of the houses, n1 is the number of agents, and m is the total length of\ud the agents’ preference lists.

We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some δ>1 (even if each woman's list is of length at most 4).

We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals/Residents problem. We show that stable matchings can have different sizes, which motivates max-spa-p, the problem of finding maximum cardinality stable matching. We prove that max-spa-p is NP-hard and not approximable within δ, for some δ>1, unless P=NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for max-spa-p.

We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals/Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.

We consider the concepts of a t-total vertex cover and a t-total edge cover (t ≥ 1),\ud which generalize the notions of a vertex cover and an edge cover, respectively. A ttotal\ud vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover\ud S of G such that each connected component of the subgraph of G induced by S has\ud least t vertices (edges). These definitions are motivated by combining the concepts\ud of clustering and covering in graphs. Moreover they yield a spectrum of parameters\ud that essentially range from a vertex cover to a connected vertex cover (in the vertex\ud case) and from an edge cover to a spanning tree (in the edge case). For various values\ud of t, we present N P-completeness and approximability results (both upper and lower\ud bounds) and FPT algorithms for problems concerned with finding the minimum size\ud of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular\ud improving on a previous FPT algorithm for the latter problem.