hu / en

MT/DP ajánló: Stabil allokációkhoz vezető utak

kti-logo-raszter

MTDP 2018/20

Ágnes Cseh – Martin Skutella

Stabil allokációkhoz vezető utak / Paths to stable allocations

A stabil allokációprobléma a stabil párosításprobléma egy általánosítása.
Egy allokációproblémában az adott páros gráf élein kapacitások, csúcsain pedig kvóták
találhatók. Cikkünkben a központi koordináció nélküli folyamatokat vizsgáljuk. Ebben a
kérdéskörben egy megengedett allokáció adott és a cél az, hogy blokkoló élek kielégítésével
stabilizáljuk ezt az allokációt. Fő kérdésünk az, hogy ilyen változásokkal eljuthatunk-e egy
valóban stabil megoldáshoz.
Mind a jobb, mind a legjobb lépések módszerét tanulmányozzuk cikkünkben.
Két determinisztikus algoritmus segítségével megmutatjuk, hogy egy valószínűséggel ér el
mindkét fent említett folyamat stabil megoldást. Meglepő módon a jobb lépések módszerének
esetében létezik polinomiális hosszú út a stabilitáshoz, míg a kézenfekvőbb legjobb lépések
módszere exponenciálisan hosszú is lehet. Tanulmányozzuk az összefüggő piacok esetét is,
ahol várható polinomiális időben konvergál stabil megoldáshoz a legjobb lépések módszere.

https://kti.krtk.hu/wp-content/uploads/2018/09/MTDP1820.pdf

2024

Már

19

H

K

Sz

Cs

P

Sz

V

26

27

28

29

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

31

1

2

3

4

5

6

7

Következő hónap >
a

2024

Már

19

H

K

Sz

Cs

P

Sz

V

26

27

28

29

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

31

1

2

3

4

5

6

7

Következő hónap >