Stabil párosítások a kombinatorikus optimalizálásban = Stable matchings in Combinatorial Optimization

Fleiner, Tamás (2006) Stabil párosítások a kombinatorikus optimalizálásban = Stable matchings in Combinatorial Optimization. Project Report. OTKA.

Preview

PDF 37301_ZJ1.pdf Download (133kB)

Abstract

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

Actions (login required)

Edit Item