Seminars

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



Прокалывающие окружности, двойственность и обобщенные диаграммы Вороного

Speaker: 
Елена Храмцова (University of Lugano (USI), Switzerland)
Date: 
Tuesday, July 21, 2015 - 13:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Цель вычислительной геометрии — создание алгоритмов, эффективно отвечающих на вопросы, возникающие в прикладных областях, которые манипулируют дискретными геометрическими объектами. Один из таких вопросов — вопрос о фигуре определенного типа, которая прокалывает (stabs) множество простых объектов. Например, определить, есть ли для данного множества из n отрезков на плоскости прямая, прокалывающая их все, можно за время O(n log n) c использованием двойственного преобразования на плоскости.[2] Если мы спросим о прокалывающей окружности (вместо прямой), элегантный результат из учебника превратится в открытую задачу. Используя другой тип двойственного преобразования, мы показали связь этой проблемы и обобщенных диаграмм Вороного (диаграммы Вороного в Хаусдорфовой метрике (Hausdorff Voronoi diagram) и диаграммы Вороного дальнего цвета (farthest-color Voronoi diagram).[1] Специальные свойства этих диаграмм позволили нам создать новый алгоритм для решения задач о прокалывающей окружности. Временная сложность решения данных задач понизилась сO(n^2) до O(n log^2 n) в случае если все отрезки множества колинеарны. В случае произвольных отрезков, наш метод понизил сложность с O(n^2 log^2 n) до O(n^2).

Основано на:
[1] M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, C. Seara, Stabbing circles for sets of segments in the plane. XVI EGC, Barcelona, 2015
[2] H. Edelsbrunner, L.J. Guibas, M. Sharir, The upper envelope of piecewise linear functions: algorithms and applications, Discrete Comput. Geom. 4 (1989), 311– 336.



Hierarchies against Sublinear Advice

Speaker: 
Александр Смаль (ПОМИ РАН)
Date: 
Monday, January 26, 2015 - 17:00
Place: 
Аудитория 402
Abstract: 

We strengthen the non-deterministic time hierarchy theorem to show that the lower bound holds against sublinear advice. More formally, we show that for any constants c and d such that 0 < c < d, there is a language in NTIME(n^d) which is not in NTIME(n^c)/n^{1/d}. The best known earlier separation could only handle o(log(n)) bits of advice in the lower bound. We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almost-everywhere hierarchy theorem for non-deterministic classes which use a sublinear amount of non-determinism, i.e., the lower bound holds on all but finitely many input lengths rather than just on in finitely many. As an application of our main result, we derive a new lower bound for NP against NP-uniform non-deterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k.



Mathematics in Synchronization and Concurrency

Speaker: 
Пётр Кузнецов (Telecom ParisTech)
Date: 
Monday, December 22, 2014 - 18:00
Place: 
Аудитория 106, ПОМИ
Abstract: 

Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Therefore, understanding fundamentals of distributed computing is of crucial importance.

The main complication here is the immense diversity of applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. In this talk, we discuss understanding of what can and what cannot be implemented in specific distributed environments, with a focus on how to apply modern mathematics in deriving new algorithms and lower bounds for distributed computing problems.



Алгоритм Эпштейна-Бейгеля решения задачи нахождения 3-раскраски графа

Speaker: 
Сергей Копелиович
Date: 
Monday, December 15, 2014 - 18:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

1. Оценки на смежные задачи: CSP, Vertex 3-List-Coloring, Edge 3-Coloring, 3-SAT.
2. Применение результатов для CSP и Vertex 3-Coloring для решения перечисленных задач.
3. Основная идея алгоритма. Простой результат за 1.34488^n.
4. Улучшения до 1.3289^n.



Прямо-двойственный метод в приближённых алгоритмах

Speaker: 
Всеволод Опарин
Date: 
Monday, December 1, 2014 - 19:00
Place: 
ПОМИ, аудитория 106
Abstract: 

Доклад будет о различных техниках получения приближенных алгоритмов через прямо-двойственный метод. Общую идею метода я расскажу на примере задачи о взвешенном покрытии множествами (демонстрация метода, f-приближение, где f — максимальное число множеств покрывающее отдельный элемент). Потом будут различные вариации того, как метод применять, на задачах о поиске кратчайшего пути в графе (зачистка прямого решения, алгоритм Дейкстра), дереве Штейнера (множественное увеличение переменных, 2-приближение) и рюкзаке (усиление неравенств, 2-приближение). Если успею, то будет еще рассказ про uncapacity facility location problem.


Pages