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.
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
