Előadó: Illés Tibor

Időpont és hely: 2015. 11. 11., 16:03, H306

Lineáris komplementaritási feladatokra (LCP) vezet számos érdekes probléma. Lineáris programozási illetve lineáris feltételes kvadratikus programozási feladatok optimalitási kritériumát LCP feladatként lehet megfogalmazni. Ebből a két példából is látszik, hogy az LCP feladatok egy része polinom időben megoldható, míg a másik része NP-tljes, reménytelenül nehezen megoldható optimalizálási feladat. Nyilvánvaló, hogy a feladat nehézségét vagy éppen hatékony megoldhatóságát az LCP mátrixának tulajdonságai határozzák meg. Az egyszerű lineáris programozási eseten túl vannak-e igazán hatékonyan megoldható, érdekes feladatosztályok? A hasznos gyakorlati feladatok mindegyik a nehezen megoldható LCP-k közé tartoznak? Mi okozza a nehézséget? Van-e remény olyan feladatok közel optimális megoldására, természetesen nem polinomiális idejű algoritmussal, amelyek fontos gyakorlati alkalmazásokból származnak?