The Open Applied Mathematics Journal

2008, 2 : 16-19
Published online 2008 April 11. DOI: 10.2174/1874114200802010016
Publisher ID: TOAMJ-2-16

Two Topics in Dominance Relations for the Unbounded Knapsack Problem

IIDA Hiroshi
Dept of Information and Management Science, Otaru University of Commerce, Otaru 047-8501, Japan.

ABSTRACT

On the unbounded knapsack problem, dominance relations play a crucial role to reduce items to be considered in a given instance. This article picks up two topics in dominance relations. One is a connection between dominance relations and polynomially solvable special cases, and the other is on unusual dominance relations.

Keywords:

Combinatorial optimisation, Unbounded knapsack problem, Dominance relation, Dominance relation, Polynomially solvable special case.