The multidimensional 0–1 knapsack problem is one of the most well-known integer
programming problems and has received wide attention from the operational research …

We consider the problem of maximizing a non-negative submodular set function f: 2N-> RR+
over a ground set N subject to a variety of packing type constraints including (multiple) …

The multiple knapsack problem (MKP) is a natural and well-known generalization of the
single knapsack problem and is defined as follows. We are given a set of n items and m bins …

Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms
and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical …

Fully polynomial approximation algorithms for knapsack problems are presented. These
algorithms are based on ideas of Ibarra and Kim, with modifications which yield better time …

Abstract The multidimensional 0-1 knapsack problem (MKP) is a resource allocation model
that is one of the most well-known integer programming problems. During the last few …

This thesis deals with the polynomial approximability of combinatorial optimization problems
which are NP-complete in their decision problem version. Different measures of …

1 Introduction.-1.1. Purpose of the Investigation.-1.2. Methodology Used.-1.3. Structure of the
Book.-2 Cutting and Packing Problems as Geometric-Combinatoric Problems.-2.1. Basic …

We consider two questions arising in the analysis of heuristic algorithms.(i) Is there a
general procedure involved when analysing a particular problem heuristic?(ii) How can …

Due to the fact that no NP-complete problem can be solved in polynomial time (unless P=
NP), many approximability results (both positive and negative) of NP-hard optimization …