Вычислительная
сложность и аппроксимируемость комбинаторных задач, связанных с комитетной
отделимостью конечных множеств
Хачай
М.Ю.
Аннотация:
В работах [1, 2] получены результаты по вычислительной и аппроксимационной сложности задачи MASC о минимальном аффинном разделяющем комитете для конечных множеств . В частности, показано, что эта задача NP трудна и не принадлежит классу Apx (в предположении, что ). Тем не менее, открытыми оставались вопросы получения оценок порога ее эффективной аппроксимируемости и оценки вычислительной сложности ряда важных для приложений частных случаев задачи, получаемых наложением дополнительных ограничений, например, фиксации размерности пространства. В настоящей статье приводится нижняя оценка порога полиномиальной аппроксимируемости задачи в общем случае и обосновывается труднорешаемость задачи в пространствах фиксированной размерности, большей единицы. В частности, показывается, что задача о комитетной отделимости остается труднорешаемой, даже будучи сформулированной на плоскости (т. е. в наиболее простом нетривиальном случае). Справедливость этого факта следует из полиномиальной сводимости к исследуемой задаче известной задачи PC о покрытии прямыми конечного множества на плоскости, труднорешаемость которой доказана [3]. Методика сведения представляет собой модификацию методики, описанной в [4], использовавшейся в этой работе для обоснования труднорешаемости задачи о кусочно-линейной отделимости конечных множеств на плоскости.
Литература:
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20