Stable matchings in Combinatorial Optimization  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
37301
Type F
Principal investigator Fleiner, Tamás
Title in Hungarian Stabil párosítások a kombinatorikus optimalizálásban
Title in English Stable matchings in Combinatorial Optimization
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Starting date 2002-01-01
Closing date 2005-12-31
Funding (in million HUF) 1.940
FTE (full time equivalent) 0.00
state closed project





 

Final report

 
Results in Hungarian
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.
Results in English
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.
Full text http://real.mtak.hu/153/
Decision
Yes





 

List of publications

 
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




Back »