Dobrovoczki Péter: Facets from gadgets (Adam N. Letchford és Anh Vu cikke alapján)

EGERVÁRY SZEMINÁRIUM

Absztrakt: We present a new tool for generating cutting planes for NP-hard
combinatorial optimisation problems. It is based on the concept of
gadgets - small subproblems that are ``glued'' together to form hard
problems - which we borrow from the literature on computational
complexity. Using gadgets, we are able to derive huge (exponentially
large) new families of strong (and sometimes facet-defining) cutting
planes, accompanied by efficient separation algorithms. We illustrate
the power of this approach on the stable set and clique partitioning
problems.

  Minden érdeklődőt szeretettel várunk!