Том 14, серия 1, номер 2, 2007 г., Стр. 95-101
УДК 519.176
В. В. Шенмайер
Алгоритм приближённого решения одномерной задачи о последовательности медиан
Аннотация:
Задача о последовательности медиан (online median) заключается в отыскании последовательности вложенных медиан возрастающей мощности. Рассматривается частный случай задачи, когда клиенты и предприятия расположены в точках вещественной прямой. Лучший известный алгоритм для одномерного случая имеет относительную оценку точности решений 8. Предлагается полиномиальный алгоритм с оценкой точности 5,83.
Шенмайер В. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Росси
е-mail: shenmaier@mail.ru
Статья поступила 11 сентября 2006 г.
Исправленный вариант — 9 января 2007 г.
