ГлавнаяАрхивМодификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках

Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | Прикладная дискретная математика. 2013. № 2(20).

В работе 1985 г. Дж. Лагариас и А. Одлыжко предложили метод решения вычислительной задачи о рюкзаке, основанный на её сведении к задаче поиска короткого вектора в решётке специального вида. Метод Лагариаса — Одлыжко позволяет решать «практически все» задачи о рюкзаках, обладающие малой плотностью. В настоящей работе метод Лагариаса — Одлыжко решения задачи о рюкзаке модифицируется применительно к случаям обобщённой задачи о рюкзаке и систем задач о рюкзаках. Система задач о рюкзаках вводится в настоящей работе как конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Определяются множества значений плотности обобщённых задач о рюкзаках и систем задач о рюкзаках, такие, что модифицированные методы позволяют решать «практически все» обобщённые задачи о рюкзаках и системы задач о рюкзаках, обладающие плотностью из этих множеств.
  • Title Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках
  • Headline Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(20)
  • Date:
  • DOI
Ключевые слова
метод Лагариаса — Одлыжко, задача о рюкзаке, обобщённая задача о рюкзаке, системы задач о рюкзаках, Lagarias — Odlyzhko method, knapsack problem, generalized knapsack problem, systems of knapsack problems
Авторы
Ссылки
Coster M. J., Joux A., LaMacchia B. A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. No. 2. P. 111-128.
Boas P. Another NP-complete problem and the complexity of computing short vectors in a lattice // Tech. rep. 8104, University of Amsterdam, Department of Mathematics, Netherlands, 1981. 10 p.
Brickell E. F. Solving low-density knapsacks // Advances in Cryptology. Proc. Crypto'83. Plenun Press, 1984. P. 25-37.
Odlyzko A.M. and Lagarias J. C. Solving low-density subset sum problems // J. Association for Computing Machinery. 1985. V.32. No. 1. P. 229-246.
Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations. Plenum Press, 1972. P. 85-103.
Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | Прикладная дискретная математика. 2013. № 2(20).
Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | Прикладная дискретная математика. 2013. № 2(20).
Полнотекстовая версия