Home

Семинар 1 сентября 2005 года

Четверг, 1 сентября, комната 106. Начало в 17:30.

Докладчик: А. Бабурин (Новосибирск).

Тема: Задачи выбора подмножества векторов с максимальной суммой: алгоритмы и сложность.

Abstract

Источник сообщений передает повторяющийся импульс неизвестной формы. Через канал передачи на приемник поступает и накапливается последовательность импульсов, искаженная аддитивным шумом. Моменты времени появления импульсов в принятой зашумленной последовательности неизвестны. Требуется обнаружить импульсы в принятой последовательности. Следуя принципу максимального правдоподобия, эта задача сводится к задаче выбора подмножества векторов с максимальной суммой.

Показано, что в случае произвольного (не ограниченного) числа импульсов задача полиномиально разрешима (для $ L_1, L_2, L_infty $ норм в пространстве исходных векторов). В случае фиксированного числа импульсов задача полиномиально разрешима для норм $ L_1 $ и $ L_infty $, для нормы $ L_2 $ --- NP-трудна. В последнем случае построен приближенный алгоритм с оценками качества и представлены условия его полиномиальности и асимптотической точности.