Том 24, номер 2, 2017 г., Стр. 87-106

УДК 519.157.1
Чухров И. П.
О доказательстве минимальности покрытий через обобщение понятия независимости

Аннотация:
Для задачи о покрытии конечного множества предложен метод получения нижних оценок длины кратчайшего и сложности минимального покрытия, основанный на понятии независимого семейства множеств. Для задачи минимизации булевых функций
построены функции и покрытия гранями множества их единичных вершин, для которых достижимы предложенные нижние оценки при пяти и более переменных. Основанные на независимых множествах нижние оценки оказываются недостижимы и не могут использоваться в качестве достаточных условий минимальности для таких функций.
Библиогр. 11.

Ключевые слова: задача о покрытии множества, сложность, кратчайшее покрытие, минимальное покрытие, независимое множество, нижняя граница, условие минимальности.

DOI: 10.17377/daio.2017.24.540

Чухров Игорь Петрович ¹
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056 Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 27 апреля 2016 г.
Исправленный вариант — 17 ноября 2016 г.

Литература

[1] Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. 2000. Сер. 2. Т. 7, № 2. С. 22–46.

[2] Забиняко Г. И. Реализация алгоритмов решения задачи о покрытии множеств и анализ их эффективности // Вычисл. технологии. 2007. Т. 12, № 6. С. 50–58.

[3] Леонтьев В. К. Дискретная оптимизация //Журн. вычисл. математики и мат. физики. 2007. Т. 47, № 2. С. 338–352.

[4] Чухров И. П. О мерах сложности комплексов граней в единичном кубе // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 77–94.

[5] Чухров И. П. О задаче минимизации для одного множества булевых функций //Дискрет. анализ и исслед. операций. 2015.Т. 22, №3. С. 75–97.

[6] Al-Shihabi S., Arafeh M., Barghash M. An improved hybrid algorithm for the set covering problem // Comput. Ind. Eng. 2015. Vol. 85. P. 328–334.

[7] Coudert O. On solving covering problems // Proc. 33rd Design Automation Conf. (Las Vegas, NV, June 3–7, 1996). New York: ACM, 1996. P. 197–202.

[8] Coudert O., Sasao T. Two-level logic minimization // Logic synthesis and verification. Norwell, MA: Kluwer Acad. Publ., 2002. P. 1–27. (Springer Int. Ser. Eng. Comp. Sci.; Vol. 654).

[9] Gao C., Yao X., Weise T., Li J. An efficient local search heuristic with row weighting for the unicost set covering problem // Eur. J. Oper. Res. 2015. Vol. 246, No. 3. P. 750–761.

[10] Sapkota N., Reilly C. H. Simulating realistic set covering problems with known optimal solutions // Comput. Ind. Eng. 2011. Vol. 61, No. 1. P. 39–47.

[11] Vasko F. J., Lu Y., Zyma K. What is the best greedy-like heuristic for the weighted set covering problem? // Oper. Res. Lett. 2016. Vol. 44, No. 3. P. 366–369.