Тезисы докладов

Математическая кибернетика

Рассматривается задача матроидной аппроксимации, самая общая постановка которой такова. Пусть K(V) - некоторый класс матроидов на конечном множестве V. Для заданной системы независимости S на множестве V найти матроид M из K(V), который в каком-то смысле является самым близким к системе S. Мера близости системы S и матроида M может определяться по-разному в различных постановках.

Исследован вариант задачи матроидной аппроксимации, эквивалентный задаче о наибольшем независимом множестве вершин произвольного графа. Предложен алгоритм поиска аппроксимирующего матроида разбиения, который можно рассматривать как приближенный алгоритм решения задачи о наибольшем независимом множестве вершин. Приведены оценки погрешности предложенного алгоритма.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии

[Головная страница] [Конференции] [СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации 06-Jul-2012 (11:45:21)