29275

Автор(ов): 

1

Параметры публикации
Тип публикации: 
Доклад
Название: 
Спектральные нижние оценки затрат связывающей сети
Электронная публикация: 
Да
ISBN/ISSN: 
ISBN 978-5-91450-151-5
Наименование конференции: 
12-е Всероссийское совещание по проблемам управления (ВСПУ XII, Москва, 2014)
Наименование источника: 
Труды XII Всероссийского совещания по проблемам управления (ВСПУ-2014, Москва)
Город: 
Москва
Издательство: 
ИПУ РАН
Год издания: 
2014
Страницы: 
1959-1970
Аннотация
Рассматривается задача поиска оптимальной связывающей сети, обеспечивающей заданный набор связей между вершинами некоторого множества. Критерий оптимизации – суммарные затраты вершин сети, зависящие от входящих и исходящих из вершины потоков. Формулируется общая модель, подробно исследуется случай аддитивных функций затрат, для которых затраты вершины сети складываются из затрат, зависящих от степени вершины, и затрат, зависящих от протекающего через вершину потока. Вычисление нижней оценки затрат оптимальной сети сводится к вычислению нижних оценок отдельно для первого и второго слагаемого функции затрат. Оптимальные сети находятся для случая, когда затраты вершины зависят от ее степени. Для функции затрат, зависящей от протекающего потока предлагаются нижние оценки с использованием результатов спектральной теории графов.
Библиографическая ссылка: 
Губко М.В. Спектральные нижние оценки затрат связывающей сети / Труды XII Всероссийского совещания по проблемам управления (ВСПУ-2014, Москва). М.: ИПУ РАН, 2014. С. 1959-1970.