Archiv zpráv a událostí

Z fakulty

  • Informatické kolokvium 6. 3. Backdoors to Tractability for Constraint Satisfaction

    Informatické kolokvium 6. 3. 2018, 14:00 posluchárna D2
    RNDr. Robert Ganian, Ph.D., Algorithms and Complexity Group, TU Wien
    Backdoors to Tractability for Constraint Satisfaction
    Abstrakt: Constraint Satisfaction (CSP) is one of the most studied NP-complete
    problems, with numerous applications in both theory and practice and featuring
    its own dedicated conference. A significant amount of research has targeted the
    identification of classes of CSP instances which are polynomially tractable;
    this has led to celebrated results such as Schaefer's Dichotomy Theorem and
    Bulatov's recent proof of the Feder-Vardi Dichotomy Conjecture. Such classes of
    instances are often called "islands of tractability".

    In this talk, we will present techniques and recent developments on solving CSP
    instances that lie outside of an island of tractability. In particular, we will
    use the notion of "backdoors" to capture the distance of an instance from an
    island of tractability and show how these backdoors can be exploited to obtain
    algorithms for CSP with good runtime guarantees.

    Webová adresa