Improved time and space complexity for Kianfar's inequality rotation algorithm

D. El Baz, M. Elkihel, L. Gely and G. Plateau

European Journal of Industrial Engineering, 2009, vol. 3, issue 1, 90-98

Abstract: In this paper, constraint rotation techniques are considered for preconditioning 0–1 knapsack problems. These techniques permit one to generate new inequalities by means of rotation of the original ones in order to approach the convex hull associated with the feasible integer points. The time and space complexities of Kianfar's inequality rotation algorithm for combinatorial problems are improved. A revisited algorithm with order of (nC) and order of (C) representing, time and space complexity, respectively, is proposed, where C is smaller than the knapsack capacity. [Submitted 12 April 2008; Accepted 26 May 2008]

Keywords: knapsack problems; constraint rotation techniques; lifting; dynamic programming; Kianfar; inequality rotation; convex hull. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=21593 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:3:y:2009:i:1:p:90-98

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().