Graphical Algorithm for the Knapsack Problem

Авторы: Лазарев А.А., Сальников А.М., Баранов А.В.
Сборник: Proceedings of the 11th International Conference on Parallel Computing Technologies, PaCT 2011
Том: 6873
Год издания: 2011
Место издания: Springer-Verlag Berlin
Первая страница: 459
Последняя страница: 466
DOI: 10.1007/978-3-642-23178-0
Аннотация: We consider a modification of dynamic programming algorithm (DPA), which is called as graphical algorithm (GA). For the knapsack problem (KP) it is shown that the time complexity of GA is less than the time complexity of DPA. Moreover, the running time of GA is often essentially reduced. GA can also solve big scale instances and instances, where the parameters are not only positive integer. The paper outlines different methods of parallelizing GA taking into account its main features and advantages to various parallel architectures, in particular by using OpenCL and MPI framework. Experiments show that "hard" instances of KP for GA have correlation pj kwj for all j, where pj and wj are utility and capacity of item j = 1, 2, . . . , n.
Добавил в систему: Лазарев Александр Алексеевич

	ИСТИНА	Войти в систему Регистрация
	ИПМех РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА