hu / en

Megjelent Biró Péter és szerzőtársai tanulmánya a Mathematical Programming folyóiratban

Mathematical Programming

Cutoff stability under distributional constraints with an application to summer internship matching

Haris Aziz, Anton, Baychkov, Péter Biró

Abstract

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 study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restricted model with disjoint regional quotas. Our first result is that checking its existence is NP-hard. We then show that a cutoff stable matching exists not just for the summer internship problem but also for the general matching model with arbitrary heredity constraints. We present an algorithm to compute a cutoff stable matching and show that it runs in polynomial time in our special case of summer internship model. However, we also show that finding a maximum size cutoff stable matching is NP-hard, but we provide a Mixed Integer Linear Program formulation for this optimisation problem.

→ Tovább a teljes tanulmányra.

2024

Ápr

20

H

K

Sz

Cs

P

Sz

V

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

Következő hónap >
a

2024

Ápr

20

H

K

Sz

Cs

P

Sz

V

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

Következő hónap >