Kaj imata skupnega kombinatorična optimizacija in realna algebraična geometrija

V kombinatorični optimizaciji se ukvarjamo z iskanjem optimuma linearne ali kvadratične funkcije nad končno množico, ki pa je praviloma  zelo velika in povezana s kakšno bazno kombinatorično množico (kombinacije, permutacije,…).

V realni algebraični geometriji študiramo rešitve polinomski enačb in neenačb, posebno pozornost pa je deležen tudi problem, ali je dani polinom nenegativen nad dano mnočico točk, definirano s polinomskimi enačbami in neenačbami. 

V zadnji desetletjih se je izkazalo, da lahko z metodami matematične optimizacije, še posebej s semidefinitnim programiranjem, zelo učinkovito pristopimo k reševanju obeh vrst problemov, kar bomo tudi predstavili na seminarju.