Том 7, серия 1, номер 4, 2000 г., Стр. 111-125

УДК 519.176
В. В. Шенмайер
Обобщение понятия ранговой функции матроида

Аннотация:
Рассматриваются две функции, являющиеся обобщениями ранговых функций системы независимости и, в частности, ранговой функции матроида. В терминах данных функций определена точность, с которой жадный алгоритм позволяет решать задачу целочисленного программирования с линейным целевым функционалом на максимум. Установлена связь между оптимальностью жадного алгоритма и субмодулярностью ранговых функций. В качестве следствия показано, что задача коммивояжера в неориентированном графе на максимум разрешима алгоритмом «иди в самый далекий непройденный город» с относительной точностью 1/2.
Ил. 1, библиогр. 6. 

Шенмайер В. В. ¹ 
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 1 июля 2000 г.