Том 1, номер 2, 1994 г., Стр. 67-99

УДК 519.854
С. В. Севастьянов
Нестрогое суммирование векторов в задачах теории расписаний

Аннотация:
Рассматриваются конечные семейства векторов на плоскости, сумма которых равна нулю, а норма каждого вектора не превосходит единицы. Конструктивно доказывается возможность нестрогого суммирования всякого такого семейства в выпуклом неограниченном множестве, содержащем точку нуль, все диаметры которого имеют длину (в заданной норме) не меньше единицы. В случае, когда норма одного из диаметров множества меньше единицы на сколь угодно малую величину, проверка существования нестрогой суммируемости заданного семейства векторов в данном множестве становится NP-трудной проблемой в сильном смысле. Применение алгоритма нестрогого суммирования к трем задачам теории расписаний для трех машин позволяет за полиномиальное время вычислять их приближенные расписания с оценками точности, не зависящими от числа работ. 
Ил. 3, библиогр. 22.

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

Статья поступила 4 января 1994 г.