Matchings with Simplest Semiorder Preference Relations
Приведены сведения о системе приема в вузы России на основании результатов Единого государственного экзамена (ЕГЭ). Построена математическая модель выбора абитуриентом вузов для подачи заявлений. На основе спрогнозированного выбора абитуриентов смоделирована приемная кампания. Показаны недостатки существующего механизма зачисления абитуриентов в вузы.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.
A common feature of the Hungarian, Irish, Spanish and Turkish higher education admission systems is that students apply for programmes and are ranked according to their scores. Students who apply for a programme with the same score are tied. Ties are broken by lottery in Ireland, by objective factors in Turkey (such as date of birth) and by other precisely defined rules in Spain. In Hungary, however, an equal treatment policy is used, students applying for a programme with the same score are all accepted or rejected together. In such a situation there is only one decision to make, whether or not to admit the last group of applicants with the same score who are at the boundary of the quota. Both concepts can be described in terms of stable score-limits. The strict rejection of the last group with whom a quota would be violated corresponds to the concept of H-stable (i.e. higher-stable) score-limits that is currently used in Hungary. We call the other solutions based on the less strict admission policy as L-stable (i.e. lower-stable) score-limits. We show that the natural extensions of the Gale–Shapley algorithms produce stable score-limits, moreover, the applicant-oriented versions result in the lowest score-limits (thus optimal for students) and the college-oriented versions result in the highest score-limits with regard to each concept. When comparing the applicant-optimal H-stable and L-stable score-limits we prove that the former limits are always higher for every college. Furthermore, these two solutions provide upper and lower boundaries for any solution arising from a tie-breaking strategy. Finally we show that both the H-stable and the L-stable applicant-proposing score-limit algorithms are manipulable.