Leírás
A SET-COVER probléma adott hipergráfra a minimális lefogó ponthalmaz megtalálása. 1974 körül egymástól függetlenül Lovász, Stein és Johnson megmutatták, hogy a mohó algoritmus, azaz, amikor minden lépésben egy olyan elemet választunk, amelyet a legtöbb eddig le nem fogott halmaz tartalmaz, jó közelítést ad, és ez a jó közelítés a frakcionális (tehát az LP relaxációs) megoldástól sincs távol. Ezt az eredményt általánosítottuk A. Polyanskii-val többszörös lefogó ponthalmaz keresésére [MN,AP: Approximating set multi-covers, Eur.J.Comb., vol. 67 (2018)].
Legújabban hárman dolgozunk azon, hogyan lehetne a következő CIP (Covering Integer Program) esetére a módszert tovább általánosítani.
Adott egy mátrix, A, melynek elemei 0 és 1 közöttiek. Keressük azt a nem-negatív egészekből álló x vektort, melyre a c^Tx skaláris szorzat minimális az Ax \geq 1 feltétel mellett, ahol c egy pozitív vektor.
Az előadás célja az eddig általunk elért eredmény bemutatása, és segítségkérés. Valahogy sehogy se tudjuk happy end-del zárni a kérdést. Kell még egy jó ötlet (ember).