Minimal Equivalent Binary Knapsack Inequalities

Autor:	Gary J. Koehler
Rok vydání:	2011
Předmět:	Combinatorics Discrete mathematics Computational complexity theory Knapsack problem Continuous knapsack problem General Engineering Binary number Subset sum problem Oracle Mathematics Exponential function Integer (computer science)
Zdroj:	INFORMS Journal on Computing. 23:425-429
ISSN:	1526-5528 1091-9856
DOI:	10.1287/ijoc.1100.0408
Popis:	It is known that a knapsack inequality can be reduced to one having the same solutions but with “minimal” integer coefficients. Although this procedure is not practical because an exponential amount of work may be required to find such minimal equivalent knapsacks, knowledge of minimal equivalent knapsacks can reduce hard knapsacks to trivial ones, as we show for both Todd and Avis knapsacks. In this paper, we show that even with an oracle able to supply minimal equivalent knapsacks at no computational cost, their practical value may not materialize because there are minimal knapsack inequalities with exponential values.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c5736dc2bd234979f89db1abc7454d35 https://doi.org/10.1287/ijoc.1100.0408 Zobrazit plný text záznamu Plný text ve formátu PDF