СКЛАДНІСТЬ ЙМОВІРНІСНИХ ПРОЦЕДУР АНАЛІЗУ СТІЙКОСТІ ЦІЛОЧИСЛОВИХ ЗАДАЧ БУЛЕВОГО ПРОГРАМУВАННЯ

Ліщук Наталія Вікторівна, аспірантка Східноєвропейського національного університету ім. Лесі Українки, м. Луцьк

pages 54-58

DOI: 10.1615/JAutomatInfScien.v47.i5.70

Показано, що для задач про покриття (які відрізняються однією позицією матриці обмежень) не існує поліноміальних -ймовірнісних процедур аналізу стійкості  при

  1. Fernandez-Baca D., Benkatachalam B. Sensitivity analysis in combinatorial optimization // handbook of approximation algorithms and metaheuristics (ed. T. Guzalez). — 2007. — Chapman&Hall / CRC Computer and Information Science Series. — P. 30-1–30-29.
  2. Михайлюк В.А. Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации // Кибернетика и системный анализ. — 2012. — 48, № 6. — С. 3–10.
  3. Михайлюк В.А. Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации // Кибернетика и системный анализ. — 2010. — 46, № 2. — С. 134–141.
  4. Михайлюк В.A., Лищук Н.В. Анализ устойчивости задачи о ранце: один отрицательный результат // Кибернетика и системный анализ. — 2013. — 49, № 2. — С. 48–51.
  5. Goldreich O. Computational complexity. A conceptual perspective. — Cambridge University Press, 2008. — 606 p.
  6. Hromkovich J. Design and analysis of randomized algorithms. Introduction to design paradigms. — Berlin; Heidelberg: Springer-Verlag, 2005. — 279 p.
  7. Кузюрин Н.Н., Фомин С.А. Сложность вычислений и анализ алгоритмов. — М.: МФТИ, 2007. — 312 с.
  8. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программирования // Журн. вычисл. математики и матем. физики. — 1988. — 28, № 10. — С. 1475–1481.
  9. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — Киев : Наук. думка, 1985. — 210 с.
  10. Сергиенко И.В., Филоненко Н.В. Решение некоторых задач устойчивости в целочисленном линейном программировании // Докл. АН УССР. Сер. А. — 1982. — № 6. — С. 79–82.