Алгоритмы с оценками для некоторых задач поиска подмножества и подпоследовательности векторов в евклидовом пространстве тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Романченко Семён Михайлович

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ПОИСКА ПОДМНОЖЕСТВА И ПОДПОСЛЕДОВАТЕЛЬНОСТИ ВЕКТОРОВ В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ

01.01.09— дискретная математика и математическая

кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

005554625

6 НОЯ 2014

Новосибирск — 2014

005554625

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. C.JI. Соболева Сибирского отделения Российской академии наук.

Научный руководитель:

Кельманов Александр Васильевич, доктор физико-математических наук, главный научный сотрудник.

Официальные оппоненты:

Ильев Виктор Петрович, доктор физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского», математический факультет, кафедра прикладной и вычислительной математики, профессор.

Тахонов Иван Иванович, кандидат физико-математических наук, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет», механико-математический факультет, кафедра теоретической кибернетики, доцент.

Ведущая организация: Федеральное государственное бюджетное учреждение науки «Институт математики и механики им. H.H. Кра-совского Уральского отделения Российской академии наук».

Защита состоится 26 ноября 2014 г. в 16 час. 30 мин. на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. C.JI. Соболева Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. C.JI. Соболева Сибирского отделения Российской академии наук и на сайте института www.math.nsc.ru.

октября 2014 г.

Учёный секретарь диссертационного совета

д.ф.-м.н.

Ю.В. Шамардин

Общая характеристика работы

Актуальность работы1. Объектом исследования настоящей работы являются проблемы дискретной оптимизации. Предмет исследования — труднорешаемые экстремальные задачи, которые индуцируются фундаментальной проблемой классификации, возникающей в широком спектре приложений. Цель исследования — построение эффективных алгоритмов с гарантированными оценками точности для решения этих задач.

Рассматриваемые в работе задачи возникают, в частности, в анализе данных и распознавании образов, в математической статистике, в теории приближения и комбинаторной геометрии. Они моделируют простейшую в содержательном плане и в то же время актуальную для многих естественно-научных и технических приложений проблему поиска в конечном множестве (или в конечной последовательности) объектов заданного числа похожих элементов. Формализация этой проблемы, например, в виде задачи аппроксимации по критерию минимума суммы квадратов уклонений индуцирует несколько полиномиально эквивалентных экстремальных задач, которые, как установлено совсем недавно, NP-трудны в сильном смысле2'3. Мотивацией исследования послужило отсутствие каких-либо полиномиальных алгоритмов с доказуемыми оценками точности для решения этих задач.

В работе исследовались две совокупности труднорешаемых задач. Первая включает задачи поиска подмножества, вторая — задачи поиска подпоследовательности.

Полиномиально эквивалентные задачи из первой совокупности имеют следующие формулировки:

1. В конечном множестве векторов евклидова пространства найти подмножество заданной мощности, минимизирующее сумму квадратов расстояний от элементов подмножества до его центра, который определяется как среднее значение по всем элементам подмножества.

2. В конечном множестве векторов евклидова пространства найти такое подмножество заданной мощности, что сумма квадратов всевозможных попарных расстояний между его элементами минимальна.

1 Работа выполнена при поддержке грантов РФФИ №№09-01-00032, 10-07-00195, 12-01-00090, 12-01-33028 мол-а-вед, 13-07-00070.

2Кельманов A.B., Пяткин A.B. NP-полнота некоторых задач выбора подмножества векторов // Дискрет, анализ и исслед. операций. 2010. Т. 17, №5. С. 37-45.

3Кельманов A.B., Пяткин A.B. О сложности некоторых задач выбора подпоследовательности векторов // Журн. вычисл. математики и мат. физики. 2012. Т. 52, № 12. С. 2284-2291.

3. Найти разбиение конечного множества векторов евклидова пространства на такие кластеры, что один из них имеет заданную мощность, оставшиеся кластеры одноэлементны, а сумма квадратов расстояний от элементов кластеров до их центров минимальна.

Задачи из второй совокупности в постановочном плане близки к сформулированным выше задачам. Отличие состоит в том, что входами задач являются не множества, а последовательности. В каждой из этих задач требуется найти подпоследовательность, имеющую заданное число членов, при ограничении на номера включаемых в неё векторов: разность между номерами последующего и предыдущего векторов, входящих в подпоследовательность, ограничена сверху и снизу заданными константами. В задачах, связанных с анализом временных рядов (сигналов) , эти константы соответствуют минимальному и максимальному допустимому интервалу между двумя последовательными повторами похожих элементов.

Цель работы — обоснование приближенных алгоритмов, обеспечивающих решение задач из этих совокупностей за полиномиальное время с априорно доказуемой точностью; поиск подклассов и специальных случаев этих задач, допускающих построение точных псевдополиномиальных алгоритмов и полностью полиномиальных приближенных схем, обоснование таких алгоритмов и схем.

Основные результаты.

1. Для евклидовой задачи поиска в конечном множестве подмножества фиксированной мощности и для евклидовой задачи поиска в конечной последовательности подпоследовательности фиксированной длины по критерию минимума суммы квадратов расстояний от элементов подмножества (подпоследовательности) до его (её) геометрического центра:

а) построены приближённые полиномиальные алгоритмы и установлена гарантированная достижимая оценка 2 точности этих алгоритмов;

б) обоснованы точные псевдополиномиальные алгоритмы для случая, когда размерность пространства фиксирована, а компоненты векторов целочисленны.

2. Установлено, что для общих случаев задач из п. 1 не существует полностью полиномиальных приближённых схем (ГРТАБ). если

и такая схема построена для задачи поиска подмножества для случая фиксированной размерности пространства.

Научная новизна. Все результаты, представленные в диссертации, являются новыми. Факт несуществования схемы Г РТА Б для рассматриваемых задач установлен впервые. До настоящего времени для

этих задач отсутствовали какие-либо эффективные алгоритмы с оценками точности.

Методы исследований. Основными инструментами исследований служили методы дискретной оптимизации и геометрии. Эффективная разрешимость задач устанавливалась конструктивно (алгоритмически). При обосновании точности приближенных алгоритмов строились оценки, дающие гарантированные границы уклонения алгоритмических решений от оптимальных.

Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты могут быть использованы, в частности, при решении геометрических задач дискретной оптимизации, в математической теории анализа данных и распознавания образов, а также в теории приближения. Подходы к построению алгоритмов и технические приёмы, предложенные в работе, могут использоваться для исследования новых задач в указанных областях. Разработанные алгоритмы могут быть использованы в приложениях, связанных с анализом данных и распознаванием образов.

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

Личный вклад автора. Все выносимые на защиту результаты получены автором лично. Постановки исследуемых задач предложены научным руководителем. Подходы к построению алгоритмов и идеи по их реализации найдены совместно. Доказательства утверждений выполнены автором. Конфликт интересов с соавторами отсутствует.

Апробация работы. Результаты диссертации докладывались на следующих российских и международных конференциях: IV и V Всероссийские конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2009, 2012), 15-я и 16-я Всероссийские конференции «Математические методы распознавания образов» (г. Петрозаводск, 2011, г. Казань 2013), XIV Всероссийская конференция «Математическое программирование и приложения» (г. Екатеринбург, 2011), XV и XVI Байкальские международные школы-семинары «Методы оптимизации и их приложения» (г. Иркутск, 2011, 2014), 9-я международная конференция «Интеллектуализация обработки информации» (г. Будва, Черногория, 2012), международная конференция «Дискретная оптимизация и исследование операций» (г. Новосибирск, 2013), IV-я международная конференция «Optimization and applications» (Petrovac, Montene-

gro, 2013).

Публикации. По результатам исследований опубликовано 16 работ. В их числе 5 статей в журналах, входящих в список ВАК РФ (из них 4 — в переводных журналах, входящих в международные системы цитирования Web of Science и Scopus); 4 статьи опубликовано в рецензируемых трудах российских и международных конференций и 7 — в виде тезисов докладов.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключенней списка цитируемой литературы, содержащей 62 источника. Работа изложена на 81 странице, содержит 5 рисунков.

Содержание работы

Во введении обоснована актуальность темы диссертационной работы, приведено краткое изложение содержания работы, сформулированы основные выносимые на защиту результаты.

В первой главе анализируются оптимизационные модели (содержательных проблем поиска похожих элементов), которые индуцируют дискретные экстремальные задачи, близкие в постановочном плане к задачам, рассматриваемым в диссертационной работе. Общей чертой этих моделей является подход, основанный на аппроксимации данных по критерию минимума суммы квадратов уклонений. Одной из наиболее известных (более полувека) экстремальных задач, возникающих в рамках этого подхода является задача MSSC (Minimum-Sum-of-Squares Clustering)4. В этой задаче требуется разбить заданное множество векторов евклидова пространства на семейство непустых подмножеств (кластеров) так, чтобы минимизировать сумму по всем подмножествам суммы квадратов расстояний от элементов подмножества до его геометрического центра. Под геометрическим центром множества понимается среднее арифметическое векторов, входящих в это множество. Искомые кластеры трактуются как подмножества, элементы которых соответствуют похожим (по указанному критерию) объектам.

В сотнях опубликованных работ были обоснованы разнообразные алгоритмы решения задачи MSSC и её специальных случаев, предложена масса полиномиальных эвристических алгоритмов (без каких-либо теоретических гарантий по точности), ориентированных на решение индивидуальных (прикладных) задач. Однако факт труднорешаемости

4Jain А.К., Data clustering: 50 years beyond K-means // Pattern Recognition Letters, Elsevier, 2010. Vol.31. P.651-666.

задачи MSSC был установлен лишь несколько лет назад5'6. Этот факт стимулировал исследования близких в постановочном плане задач. К их числу относятся задачи, рассмотренные в диссертационной работе. Эти задачи моделируют существенно более простую в содержательном плане проблему поиска всего одного подмножества похожих объектов. Статус вычислительной сложности задач, индуцированных этой проблемой, был установлен совсем недавно: эти задачи NP-трудны в сильном смысле7,8. В результате анализа существующих работ установлено, что какие-либо полиномиальные алгоритмы с оценками точности для решения этих задач до настоящего времени отсутствовали. Этот факт определил направление исследований и специфику полученных в работе результатов.

Все рассматриваемые в работе задачи индуцируются одной оптимизационной моделью. Предполагается, что в отсутствие помехи анализируемые данные описываются векторной последовательностью хп ё К', п £ Л/" = {1,..., N}, имеющей следующую структуру

{tu, если п е М., . .

^ КГ\ А А ^

vn, если п £ Jv \ A4,

где М. = {гц,...,пм} С j\f. Для обработки доступна последовательность

Уп = хп + еп, п € 7V, (2)

где еп — вектор помехи (ошибки измерения), независимый от вектора хп. Требуется, учитывая структуру (1) последовательности хп, минимизировать функционал

S{M,w,{vi,ieAi\M}) = ^ \\хп - уп\\2 (3)

пелГ

при условии, что мощность множества М. фиксирована и равна М. Фактически, задача состоит в приближении последовательности уп последовательностью хп.

5Aloise D., DeshpandeA., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Machine Learning. 2009. Vol.75, №2. P. 245-248.

6P. Bonsma, H.Broersma, V.Patel, A. Pyatkin. The complexity of finding uniform sparsest cuts in various graph classes // Journal of Discrete Algorithms. 2012. Vol. 14, P. 136-149.

7Кельманов A.B., Пяткин A.B. NP-полнота некоторых задач выбора подмножества векторов // Дискрет, анализ и исслед. операций. 2010. Т. 17, №5. С. 37-45.

8Кельманов A.B., Пяткин A.B. О сложности некоторых задач выбора подпоследовательности векторов // Журн. вычисл. математики и мат. физики. 2012. Т. 52, №12. С. 2284-2291.

В задачах поиска подпоследовательности в дополнение к (1)-(3) предполагается, что элементы набора {тц,..., пм} удовлетворяют ограничениям

Гт;п < пт - nm_ 1 < Tmax, т = 2,...,М, (4)

где натуральные константы Тт-т и Ттах определяют допустимый интервал между двумя последовательными повторами неизвестного вектора w в последовательности (1).

Как отмечено выше, для рассматриваемых задач, вытекающих из приведенной модели, до настоящего времени какие-либо эффективные алгоритмы с оценками точности отсутствовали. Вместе с этим отметим, что параллельно с настоящим исследованием для индуцированных задач на множествах была предложена9 приближенная полиномиальная схема (PTAS). Кроме того, построены10'11 алгоритмы с оценками для некоторых актуальных обобщений рассматриваемых задач.

Во второй главе рассматриваются полиномиально эквивалентные NP-трудные в сильном смысле задачи, которые индуцируются оптимизационной моделью (1)-(3). Задачи имеют следующие формулировки.

Задача VS-2. Дано: множество У = {ух,..., у^} векторов из R9 и натуральное число М > 1. Найти: подмножество С С У векторов такое, что

у£С

где у(С) = щ Х^ес У' пРи ограничении \С\ = М на мощность искомого подмножества.

Подмножество С в этой задаче определяется набором Л4 из модели (1)-(3) так, что С = {уп\п е М}.

Задача VS-3. Дано: множество У = {yi,..., удг} векторов из К9 и натуральное число М > 1. Найти: подмножество С С у векторов такое, что

н{с) = -z и2-* min,

y€CzEC

9ШенмайерВ.В. Аппроксимационная схема для одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций. 2012. Т.19, №2. С. 92-100.

10Галашов А.Е., Кельманов A.B. 2-приближённый алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов // Автоматика и телемеханика. 2014. Т. 4. С. 5-17.

11И.И. Еремин, Э.Х. Гимади, A.B. Кельманов, A.B. Пяткин, М.Ю. Хачай. 2-приближенный алгоритм поиска клики с минимальным весом вершин и ребер // Труды Института математики и механики УрО РАН. 2013. Т.19, №2. С. 134-143.

при ограничении \С\ = М на мощность искомого подмножества.

Задача MSSC-Case. Дано: множество У = {ух,. ■ ■ ,vn} векторов из R9 и натуральное число М > 1. Найти: разбиение множества У на J = N — M+1 непустых кластеров С\, ...С j такое, что \Ci\ — М и

j

Q(Ci,..., Cj) = Y, E Hf - УРА I'2 min'

j=i уес,

где y(Cj) = ^ Y,yeCj y, j = I..., J.

Из сильной NP-трудности задач, а также ограниченности значений их целевых функций полиномами от размера входа и входных числовых данных, следует12 факт несуществования точных псевдополиномиальных алгоритмов для общего случая этих задач. На вопрос существования схемы FPTAS для общего случая этих задач отвечает

Теорема 2.1. Если P^NP, то для задач VS-2, VS-3 и MSSC-Case не существует схемы FPTAS.

Целевые функции задач связаны следующими формулами:

Q(C1,...,Cj)=F(C1), F(C) = ^H(C). (5)

Поэтому, по любому допустимому решению одной из задач можно построить допустимые решения и для остальных задач, причём оценки точности таких решений будут совпадать.

В качестве базовой в работе рассматривается задача VS-2, для её решения предложены следующие алгоритмы.

Алгоритм Ai-

Шаг 1. Для каждого у & У, найдем подмножество См (у) С У, состоящее из М ближайших к у векторов (в смысле расстояния).

Шаг 2. Выберем такой вектор уд, для которого значение целевой функции Р(См(ул)) минимально. Множество См(ул) объявим решением задачи.

Теорема 2.2. Алгоритм А\ находит 2-приближённое решение задачи VS-2 за время 0(qN2). Оценка 2 точности алгоритма достижима.

В работе обоснован точный псевдополиномиальный алгоритм для специального случая задачи VS-2, когда размерность пространства фиксирована, а компоненты входных векторов имеют целочисленные значения.

l2Garey m.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — San Francisco: Freeman, 1979. — 314 p.

Положим В — max max | (уУ |, где (у)3 — j-я компонента вектора у.

УёУ j=l,...,q

Алгоритм Л^-

Шаг 1. Построим вспомогательное множество

В = {Ь| (ьу = (vy/M; (v)j е Z, \(vy\ < MB, j = l,...,q}. (6)

Шаг 2. Для каждого вектора b € В найдём подмножество См(Ь) С У, состоящее из М ближайших к Ъ векторов.

Шаг 3. Среди построенных на шаге 2 подмножеств выберем подмножество, для которого значение целевой функции F минимально. Это подмножество объявим решением задачи.

Теорема 2.3. Если все векторы множества У имеют целочисленные компоненты, то алгоритм Л2 находит оптимальное решение задачи VS-2 за время 0(qN(2MB + 1)«).

При фиксированной размерности q пространства время работы алгоритма Л2, которое можно записать в виде 0(N(MB)q), ограничено полиномом от размера N (М < N) и максимального численного значения В входа задачи. Следовательно алгоритм псевдополиномиален.

Для случая фиксированной размерности пространства векторов, в работе построен алгоритм, реализующий схему FPTAS.

Алгоритм Аз.

Для каждого вектора у £ У выполним шаги 1-3.

Шаг 1. Вычислим параметры h = -^щгм(у,У) и где гм(у,У) — расстояние от у до М-го ближайшего к у вектора из

Шаг 2. Внутри шара с центром в точке у радиуса Н построим дискретную равномерную сетку В(у, h, Н) с шагом h.

Шаг 3. Для каждого элемента Ь е В (у, h, Н) построим множество См(Ь) С у из М ближайших к b векторов.

Шаг 4. Среди найденных на шагах 1-3 подмножеств выберем подмножество Сд с минимальным значением целевой функции F. Найденное множество Сд объявим решением задачи.

Теорема 2.4. Для любого фиксированного е S (0,1) алгоритм Аз находит (1 + е)-приближённое решение задачи VS-2 за время 0{q2N2(2^qM/e + iy).

В случае фиксированной размерности q пространства сложность алгоритма Аз можно записать в виде 0(N2(M/е)4). Поэтому в этом случае алгоритм Аз реализует схему FPTAS.

В третьей главе рассматриваются задачи на векторных последовательностях, которые индуцируются оптимизационной моделью (1)-(4). Отличие этой модели от модели, рассматриваемой во второй главе, состоит лишь в дополнительных ограничениях (4).

Рассматриваемые задачи имеют следующие формулировки.

Задача MSSC-Case-S. Дано: последовательность У = (у\,..., улг) векторов из r9, натуральные числа Тт-т,Ттак и М > 1. найти: разбиение множества Af на J = N — М + 1 непустых подмножеств Mi,...,-Mj такое, что |.Mi| = М и

J

fi{M1,...,Mj)=Yi £ ll2/m-y(^)H2^min,

j = 1 meMj

где y(Mj) = щ-у YlneM, У™ > 3 = при ограничениях (4) на

элементы подмножества Л4х.

Задача VSS-2. Дано: последовательность У — (yi,... ,Уы) векторов из r9, натуральные числа Тт-т, ттах и М > 1. найти: подмножество Л4 = {ni,..., пм} С Л/" номеров элементов последовательности такое, что

м

f2(M) = ||уПт -у(М)||2 -> min,

т=1

где у(Л4) = Yhn^M УпРи ограничениях (4) на элементы из Л4.

Задача VSS-3. Дано: последовательность У — (j/i,... ,улг) векторов из r9, натуральные числа Тт¡п, ттах и М > 1. найти: подмножество ЛЛ = {ni,... ,пм} Q ЛГ номеров элементов последовательности такое, что

м м

/з(Х) = ££|1г/п,-М2 ¿=1 j=1

минимальна, при ограничениях (4) на элементы подмножества М.

Эти задачи NP-трудны в сильном смысле, т.к. специальные случаи задач VSS-2, VSS-3 и MSSC-Case-S поиска подпоследовательности, когда Tmin = 1 и Tmax = N, эквивалентны соответствующим задачам VS-2, VS-3 и MSSC-Case поиска подмножества. Поэтому из теоремы 2.1 следует отсутствие схем FPTAS для общего случая задач поиска подпоследовательности, если P^NP.

Кроме того, целевые функции задач выбора подпоследовательности связаны формулами

MMt,. ■ -,Mj) = f2(Mi), f2(M) = JL/3(A4),

которые аналогичны формулам (5), связывающим целевые функции задач второй главы.

Для построения алгоритмов решения задачи VSS-2 используется следующая вспомогательная экстремальная

Задача 1. Дано: последовательность У — (yi,... , yjv) векторов из М9, вектор Ь £ К9, натуральные числа Tmin,Tma.x и М. Найти: набор = {ni,... ,пм} Q ЛГ номеров элементов последовательности таких, что

G(b,M) = \\Уп - Ь\\2 ->■ min, п ем

при ограничениях (4) на элементы набора АЛ.

В работе обоснована схема динамического программирования, которая позволяет находить оптимальное решение задачи 1.

Лемма 3.4. Пусть система ограничений (4) совместна. Тогда оптимальное значение целевой функции вспомогательной задачи находится по формуле

Gmin(b) = min GM(n),

n€u}\f

а значения функций См{п),п € вычисляются по следующим рекуррентным формулам:

{\\уп — Ъ\\2, если п Е Lüi,m = 1;

\\y-n — b\\2 + min Gm-i(j), если п £ ит,т = 2, ...,М, № Tm.i(n)

где

и>т = {n|l + {т- 1 )Tmin <n<N— (М — m)Tmin}, т = 1,..., М,

7m-i(n) = Ül тах{1 + (т - 2 )Tmin, п - Гтах} <j<n- Ттт},

п 6 шт, т = 2,..., М.

Теорема 3.1. Алгоритм, реализующий схему из леммы 3.4, находит оптимальное решение вспомогательной задачи. Трудоёмкость алгоритма равна 0(М(М(Ттах — Тт-т + 1) + д)).

Поскольку множители (Ттах — Тт-т + 1) и М не превосходят ЛГ, временную сложность схемы можно оценить как 0(М(д + Лг2)).

Алгоритм Л4.

Шаг 1. Для каждого п е N найдем оптимальное решение ЛЛ{уп) вспомогательной задачи и значение Ст\п{уп) оптимума.

Шаг 2. Среди построенных решений выберем решение с наименьшим значением Ст-т(уп).

Теорема 3.1. Алгоритм Л4 находит 2-приближённое решение задачи У8Э-2 за время С>(ЛГ2(д + ЛГ2)). Оценка 2 точности алгоритма достижима.

Алгоритм Л5.

Шаг 1. Построим множество В по формулам (6).

Шаг 2. Для каждого Ь € В найдем оптимальное решение М(Ь) вспомогательной задачи, вычислим значение оптимума Ст;п(Ь).

Шаг 3. Среди построенных решений выберем решение с наименьшим значением Ст-ш(Ь).

Теорема 3.3. Если все векторы последовательности (ух,..., ум) имеют целочисленные компоненты, то алгоритм Л5 находит оптимальное решение задачи УБ8-2 за время 0{Ы{К2 + ц){2МВ + I)9).

Псевдополиномиальность алгоритма при фиксированной размерности д пространства следует из того, что временная сложность алгоритма, которую можно записать в виде С(Аг3(Л/В)'1), полиномиально зависит от значений числовых данных (а именно, от В) на входе задачи.

В Заключении перечислены основные результаты диссертационной работы, описан круг возможных применений полученных результатов, обозначены перспективы дальнейших исследований.

Публикации автора по теме диссертации

Статьи в журналах

[1] Кельманов А. В., Романченко С.М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Дискрет, анализ и исследование операций,— 2011.— Т. 18, №4.— С. 61-69.

A.V. Kel'manov, S.M. Romanchenko. An Approximation Algorithm for Solving a Problem of Search for a Vector Subset // Journal of Applied and Industrial Mathematics.— 2012,- Vol. 6, №i — P. 90-96.

[2] Кельманов А. В., Романченко С. M., Хамидуллин С. А. Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Дискретный анализ и исследование операций.— 2012,— Т. 19, №3.— С. 27-38.

A.V. Kel'manov, S.M. Romanchenko, S.A. Khamidullin.

Approximation Algorithms for Some Intractable Problems of Choosing a Vector Subsequence // Journal of Applied and Industrial Mathematics.- 2012,- Vol. 6, №4.- P. 443-451.

[3] Кельманов А. В, Романченко С. M. Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика,— 2012. № 2,— С. 156-162.

A.V. Kel'manov, S.M. Romanchenko. Pseudopolynomial Algorithms for Certain Computationally Hard Vector Subset and Cluster Analysis Problems // Automation and Remote Control — 2012.— Vol. 73, № 2 — P. 349-354.

[4] Кельманов А. В., Романченко С.М., Хамидуллин С. А. Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Журнал вычислительной математики и математической физики.— 2013.— Т. 53, №1,- С. 143-153.

[5] Кельманов А. В., Романченко С. М. FPTAS для одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций - 2014.- Т.21, №3.- С. 41-52.

A.V. Kel'manov, S.M. Romanchenko. FPTAS for a Vector Subset Search Problem // Journal of Applied and Industrial Mathematics.— 2014.- Vol. 8, №3.- P. 329-336.

Труды конференций

[6] Кельманов А. В., Романченко С. М. Алгоритмы с оценками для некоторых задач поиска подмножества векторов и кластерного анализа // Математические методы распознавания образов: 15-я Всероссийская конференция (ММРО-15), г. Петрозаводск, 11-17 сентября 2011 г.: Сборник докладов. — М.: МАКС Пресс, 2011,— С.273-276.

[7] Кельманов А. В., Романченко С. М., Хамидуллин С. А. 2-приближенный алгоритм для одной задачи поиска в векторной последовательности совокупности «похожих» элементов // Математические методы распознавания образов: 15-я Всероссийская конференция (ММРО-15), г. Петрозаводск, 11-17 сентября 2011 г.: Сборник докладов. — М.: МАКС Пресс, 2011- С. 281-283.

[8] A.B. Кельманов, С.М. Романченко. Псевдополиномиальные алгоритмы для некоторых задач поиска подмножества векторов и кластерного анализа // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 23-29 июня 2011 г. Т.4: Дискретная оптимизация, Иркутск: РИО ИДСТУ СО РАН, 2011.- С. 144-149.

[9] Кельманов А. В., Романченко С. М., Хамидуллин С. А. Точные псевдополиномиальные алгоритмы для некоторых труднорешае-мых задач поиска подпоследовательности векторов // Интеллектуализация обработки информации: 9-я международная конференция. Республика Черногория, г. Будва, 16-22 сентября 2012 г.: Сборник докладов. — М.: Торус Пресс, 2012,— С. 275-278.

Тезисы докладов

[10] Кельманов A.B., Романченко С.М. Об одной задаче поиска наборов векторов // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 29 июня - 4 июля 2009. Материалы конференции. — Омск: Полиграфический центр КАН.— С. 134.

[11] Кельманов A.B., Романченко С.М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Тез. докл.

XIV-й Всероссийской конференции «Математическое программирование и приложения», г.Екатеринбург, 28 февраля - 4 марта 2011 г. Екатеринбург: УрО РАН,- С. 100.

[12] Кельманов А. В., Романченко С.М., Хамидуллин С. А. Точный псевдополиномиальный алгоритм для одной NP-трудной задачи поиска подпоследовательности векторов // Материалы V Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 2-6 июля 2012. Материалы конференции. — Омск: Изд-во Ом. гос. ун-та.— С. 134.

[13] Кельманов А. В., Романченко С. M. FPTAS для одной труднореша-емой задачи поиска подмножества векторов // Математические методы распознавания образов: 16-я Всероссийская конференция (ММРО-16), г. Казань, 6-12 сентября 2013 г.: Тезисы докладов. — М.: Торус Пресс, 2011 — С. 33.

[14] Alexander Kel'manov, Semyon Romanchenko. A fully polynomial time approximation scheme for a problem of choosing a vector subset // Proceedings of IV International Conference «Optimization and applications» (OPTIMA-2013), Petrovac, Montenegro, September 22-28, 2013.- P.89.

[15] А. В. Кельманов, С. M. Романченко. FPTAS для одной NP-трудной задачи поиска подмножества векторов // Материалы международной конференции «Дискретная оптимизация и исследование операций», DOOR-2013, Новосибирск, Академгородок, 24-28 июня 2013. — Новосибирск: Изд-во Института математики СО РАН, 2013.- С. 158.

[16] С. М. Романченко. Алгоритмы с оценками для некоторых квадратичных задач поиска подмножества и подпоследовательности векторов евклидова пространства // Материалы XVI Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 30 июня-6 июля 2014 г. Тезисы докладов. — Иркутск, ИСЭМ СО РАН, 2014.- С. 91.

Подписано в печать 15.10.2014 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. а. л. 1 Тираж 100 экз. Заказ № 229

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф.104 Тел. (383) 217-43-46, 8-913-922-19-07