Leírás
Kétféleképpen tekinthetjük 3-reguláris gráfokban az utazóügynök problémát. Egyrészt tekinthetjük a gráf éleit egységnyi hosszúságúnak, és keresünk egy minimális hosszúságú utazóügynöki bejárást - így a grafikus utazóügynök problémát kapjuk. Másrészt tekinthetjük a 3-reguláris gráf éleit tetszőleges élhosszokkal, és így egy különös speciális esetét kapjuk a metrikus utazóügynök problémának. Mindkét esetre vonatkozólag számos eredmény született az utóbbi 5-10 évben, és ezeket fogjuk áttekinteni a következő előadásban, többek között Boyd; Candrakova és Lukotka; Karp és Ravi; Boyd, Iwata és Takazawa; Haddadan, Newman és Ravi; Agarwal, Garg és Gupta; Boyd és Sebő eredményei alapján. Esetenként a minimális 2-élösszefüggő részgráf problémával is kapcsolatban vannak a kapott eredmények, így azokra is ki fogunk térni. Látszólag nagyon speciális esetben kötünk ki amikor azt feltételezzük, hogy a gráf 3-reguláris, és sokszor valamilyen élösszefüggőséget is feltételezünk, de egyelőre csak ilyen feltételezésekkel sikerült a Christofides algoritmusa által garantált 3/2-es korlátot megdönteni, és érdekes módon pont erre az algoritmusra adott extrém példák pont 3-nál nem nagyobb fokú gráfokól ("sub-cubic") kaphatóak, tehát valamilyen értelemben mégiscsak megragadja a probléma nehézségét a 3-reguláris, vagy "sub-cubic" gráfok osztálya. Az alkalmazott módszerek a kombinatorikus optimalizálás számos területéről merítenek eszközöket, így jól alkalmazhatóak a párosítások, a lineáris programozás, matroidok, konstruktív karakterizációk, fülfelbontások és leemelések, mohó jellegű algoritmusok, lokális keresés, és ez már olyan sok, hogy szinte biztos ki fog maradni valami izgalmas dolog az előadásból mielőtt kicsengetnek.