Stabil párosítások a kombinatorikus optimalizálásban  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
37301
típus F
Vezető kutató Fleiner Tamás
magyar cím Stabil párosítások a kombinatorikus optimalizálásban
Angol cím Stable matchings in Combinatorial Optimization
zsűri Matematika–Számítástudomány
Kutatóhely MTA Rényi Alfréd Matematikai Kutatóintézet
projekt kezdete 2002-01-01
projekt vége 2005-12-31
aktuális összeg (MFt) 1.940
FTE (kutatóév egyenérték) 0.00
állapot lezárult projekt





 

Zárójelentés

 
kutatási eredmények (magyarul)
Az F 037301 sz. OTKA kutatási projekt fő eredményei az alábbiak. A stabil párosítások és különböző más tudományterültek kapcsolatának kimutatása, a nempáros modellek stabil párosításait jellemző Tan-féle karakterizáció általánosítása, a stabil párosítások általánosításainak megfelelő stabil párosítás poliéderek leírása, ezen belül Rothblum leírásának kiterjesztése és általánosítása, a stabil b-párosítások egy érdekes és fontos tulajdonságának felfedezése, a stabil szobatárs probléma bizonyos általánosításainak visszavezetése az eredeti problémára, Irving algoritmusának általánosítása, a szuperstabil párosítások részbenrendezéses általánosításának kezelése, élődonoros szervátültetések során fellépő stabilitási problémák megoldása, kevés él által blokkolt párosítások problémájának bonyolultságának megállapítása, az inkrementáló algoritmusok egy fontos tulajdonságának általánosítása a nempáros modellre, az ú.n. MS párosítások általánosítása matroidokra és Delta-matroidokra, ill. a címkézett pontokon megadott fák leszámlálása a fordított Prüfer-kód segítségével. Az elért eredmények több konferencián, workshopon ill. szemináriumon hangzottak el, köztük meghívásos előadásként is. Gyümölcsöző kutatási együttműködés jött létre a Kassán kutató Katarína Cechlárovával és a glasgowi kutatócsoporttal, köztük is elsősorban David Manlove-val.
kutatási eredmények (angolul)
The main achievements of the OTKA F 037301 project are the following. Demonstration of the connection of stable matchings and other areas, generalizaton of Tan's characterization of nonbipartite stable matchings, linear descriptions of polyhedra corresponding to generalizations of stable matchings, in particular the extension and generalization of Rothblum's description, exploration of an interesting and important property of many-to-many stable matchings, reduction of certain generalizations of the stable roommates problem to the original one, generalization of Irving's algorithm, handling of the poset generalizations of superstable matchings, solving stability problems related to living-donor organ transplantations, determination of the complexity of finding a matching blocked by a minimum number of edges, generalization of an important property of incremental algorithms to the nonbipartite model, generalization of the so-called MS matchings to matroids and Delta-matroids, and enumeration of labelled trees with the help of reverse Prüfer codes. The results of the project were performed in several conferences, workshops and semiars, even as invited talks. We started a fruitful research cooperation with Katarína Cechlárová from Kosice and with the Glasgow research group, in particular with David Manlove.
a zárójelentés teljes szövege http://real.mtak.hu/153/
döntés eredménye
igen





 

Közleményjegyzék

 
Fleiner Tamás, Rob Irving és David Manlove: Efficient algorithms for generalised stable marriage and roommates, Computing Science Department of Glasgow University Technical Report, 2005
Fleiner Tamás: Some Results on Stable Matchings and Fixed Points, "The 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications" konferenciakötet, 2003
Fleiner Tamás: On Prüfer codes, EGRES Technical Report, 2005
Kataríná Cechlárová, Fleiner Tamás és David Manlove: The Kidney Exchange Game, SOR '05 konferenciakötet, 2005
Ron Aharoni és Fleiner Tamás: On a lemma of Scarf, Journal of Combinatorial Theory Ser. B, 2003
Fleiner Tamás, Frank András és Satoru Iwata: An Ordered Parity Problem for Matroids and Delta-Matroids, Operations Research Letters, 2004
Fleiner Tamás: On the stable b-matching polytope, Mathematical Social Sciences, 2003
Kataríná Cechlárová és Fleiner Tamás: On a generalizaton of the stable roommates problem, Transactions on Algoritms, 2005
David J. Abraham, Biró Péter és David F. Manlove: “Almost Stable” Matchings in the Roommates Problem, Lecture Notes in Computer Science, 2006
Biró Péter: Stable matching with incremental algorithms - The last one gets his best stable partner, 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2005
Fleiner Tamás: A fixed point approach to stable matchings and some applications, Mathematics of Operations Research, 2003




vissza »