Адрес e-mail:

Лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems»

Лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems»

28 ноября в 18:30 в Актовом зале ЛК в рамках математического кружка ФПМИ состоится лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems».


Аннотация:


Classifying complexity of different classes of optimization problems is an important research direction in Theoretical Computer Science. One prominent framework is Valued Constraint Satisfaction Problems (VCSPs) in which the class is parameterized by a "language", i.e. a set of cost functions over a fixed discrete domain. An instance of the problem is an arbitrary sum of functions fr om the language (possibly with overlapping variables), with the goal to minimize the sum. This framework can capture many classes of optimization problems such as 3-SAT, graph coloring, minimum vertex cover, submodular minimization, and others.

A series of recent papers, culminating with the works of D. Zhuk and A. Bulatov in 2017, have established a complete complexity classification of arbitrary languages. Vladimir will describe their contributions to this topic. One of the results is a reduction from general VCSPs to plain CSPs (i.e. to languages with {0,infinity}-valued functions). The key algorithmic tool that was used is a certain LP relaxation of the problem combined with the algorithm for plain CSPs.


In the second part of the talk Vladimir will consider a version of the CSP framework wh ere each variable must appear in exactly two constraints. It captures, in particular, the class of perfect matching problems, which can be solved by the Edmonds's blossom-shrinking algorithm. Vladimir will present a generalization of this algorithm that can handle "even Delta-matroid constraints". As a consequence of this, researchers settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec.


Владимир Колмогоров — профессор Института науки и техники (IST), Австрия. Он окончил Московский физико-технический институт в 1999 году. Учёную степень кандидата компьютерных наук получил в Корнельском университете в 2003 году. Основным направлением исследований Владимира является дискретная оптимизация алгоритмов для задач в компьютерном зрении и других областях.

Лекция пройдёт на английском языке.


Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li soc-yt
Яндекс.Метрика