В докладе будет рассмотрен класс задач разбиения множества на подмножества удовлетворяющие какому-то полиномиально проверяемому свойству. Известен алгоритм, который решает задачу такого вида за 2^n. Так же, известно, что если ограничиться, вместо множеств, графами ограниченной степени, то решение может быть найдено за (2-eps)^n (где eps зависит только от максимальной степени графа). Не так давно был поставлен вопрос, можно ли получить аналогичные оценки для графов ограниченной средней степени.
В докладе будет дан утвердительный ответ для некоторых частных случаев. Будет рассказан метод, позволяющий получить ускорение, в случаи если задача допускает локальные ограничения определенного вида. Будет показано, как с помощью этого метода получить оценки вида (2-eps)^n для задачи коммивояжера и нахождения хроматического числа графа и задачи о поиске кратчайшей надстроки.

В докладе будет описана технология изображающей масс-спектрометрии
(ИМС), поставлены задачи поиска характерных изображений и сегментации
ИМС-данных, а также предложены методы решения на основе тематических
моделей, марковских сетей и кластеризации.

В первой части доклада будут рассмотрены раннее существовавшие рейтинговые системы,
будет рассмотрена система TrueSkill(TM) и представлено выполненное нами улучшение этой
системы. Также будет представлена утилита для выполнения Байесовского вывода на
фактор-графах с помощью алгоритма распространения ожидания. Будут представлены
экспериментальные результаты скорости работы в зависимости от количества использованных
ядер процессора.

Во второй части будут представлены результаты работы по прогнозированию времени работы
сборщика мусора в системе Data Domain.

В докладе будут рассмотрена задача ранжирования и современные ML-методы её решения , основанные на градиентном спуске - RankNet и его расширение, LambdaRank.