Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Introduction to online algorithms

Speaker: 
Sushmita Gupta
Date: 
Monday, September 22, 2014 - 18:00
Place: 
ПОМИ РАН, Мраморный зал
Abstract: 

In this lecture we will survey the area of online algorithms using some well known examples and problems. We will look at classical approaches as well as new ones, and discuss the underlying principles and objectives that drive research in the online paradigm.



Задача редактирования графа до графа с заданными степенями

Speaker: 
Пётр Головач
Date: 
Thursday, September 18, 2014 - 18:00
Place: 
ПОМИ РАН, Мраморный зал
Abstract: 

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph $G$, non-negative integers $d,k$ and a function $\delta \colon V(G) \to \{1,...,d\}$, whether it is possible to obtain a connected graph $G’$ from $G$ such that the degree of $v$ is $\delta(v)$ for any vertex $v$ by at most $k$ edge editing operations. As the problem is NP-complete even if $\delta(v)=2$, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by $d+k$. For the special case $\delta(v)=d$, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. We also investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. In particular, we obtain polynomial-time algorithms for the Edge Editing to an Eulerian Graph problem and its directed variant.



2 11/23 - приближение для задачи о кратчайшей надстроке

Speaker: 
Евгений Служаев
Date: 
Monday, September 15, 2014 - 18:30
Place: 
Аудитория 203
Abstract: 

Будет рассказано об алгоритме Марчина Мухи и получено 2 11/23 - приближение для задачи о кратчайшей надстроке, которое является наилучшим из известных на сегодняшний день приближений для этой задачи.



Приближённые алгоритмы для Feedback vertex set

Speaker: 
Всеволод Опарин
Date: 
Monday, July 21, 2014 - 18:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.


Pages