Семинары: К. С. Кобылкин, Сложность и неприближаемость некоторых задач о наименьшей системе секущих объектов на геометрических графах

СЕМИНАРЫ


Семинар отдела математического программирования 13 ноября 2015 г. 11:30, г. Екатеринбург, ул. Софьи Ковалевской, 16, актовый зал, 3 этаж, Институт математики и механики им. Н.Н.Красовского

Сложность и неприближаемость некоторых задач о наименьшей системе секущих объектов на геометрических графах К. С. Кобылкин^ab ^a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург ^b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Аннотация: В докладе рассматривается задача о наименьшей системе секущих объектов (geometric stabbers) для системы отрезков, совпадающих с ребрами некоторого геометрического графа $G.$ Даются результаты о сложности и неаппроксимируемости (нижние оценки для разрыва целочисленности) этих задач как в случае произвольного, так и важном для приложений частном случае планарного графа $G,$ где класс секущих объектов совпадает либо с множеством кругов фиксированного радиуса, либо с классом прямых произвольной ориентации.