Обобщение понятия ранговой функции матроида

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