Seminars

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


Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.

Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.

Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.

Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.

Пятница 09.12. Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences): " Self-Verifying Finite Automata"

Speaker: 
Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences)
Date: 
Friday, December 9, 2016 - 16:00
Place: 
ауд. 311
Abstract: 

Consider a nondeterministic finite automaton $M$ over an alphabet $\Sigma$,
where the states can be either accepting, rejecting, or neutral. Let $L_a(M)$ (resp., $L_r(M)$) be the set of strings taking $M$ from the start state to an accepting state (resp., rejecting state). Then $M$ is said to be self-verifying
if $L_a(M) \cup L_r(M) = \Sigma^*$ and $L_a(M) \cap L_r(M) = \emptyset$.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of $\Sigma^*$. The language accepted by $M$ is $L_a(M)$.

Using a result of Moon, Moser [On cliques in graphs, Israel J. Math. 3, 23--28, 1965], we get an optimal simulation of self-verifying automata by deterministic finite automata. Then we study the complexity of regular operations on languages represented by self-verifying automata, and get the tight upper bounds for union ($mn$), intersection ($mn$), reversal ($2n+1$), star (${3\over 4}2^n$), left quotient ($2^n-1$), right quotient ($3^{n/3}$), and asymptotically tight upper bound for concatenation ($3^{m/3}2^n$). Next we prove that given a nondeterministic automaton $M$ with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if $M$ is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.

Pages