Browse Prior Art Database

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

IP.com Disclosure Number: IPCOM000128512D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 20 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

Given a positive integer M and n pairs of positive integers [Equation ommitted] maximize the sum Ed ipi subject to the constraints [Equation ommitted] This is the well known 0/1 knapsack problem. An algorithm is presented which finds for any [Equation ommitted] where P* is the desired optimal sum. Moreover, the algorithm runs in time [Equation ommitted] are functions depending only on s . Thus, for a fixed error, the algorithm has time complexity 4(nlogn) and space complexity 0(n). Hodificatioa of the algorithm for the general knapsack problem where the di's can be any non-negative integer results is a 0(u(e)n) computing time. A linear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that pi/ci is the same for all [Equation ommitted]

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

By

Oscar H. Ibarra and Chul E. Kim

Computer, Information, and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

0400163 11 1- Tecaica~.~Report 74-13 June, 1974 E. Rim This research teas supported by the National Science Foundation Grant GJ-35614. Cover courtesy of Ruth and Jay Leavitt Fast Approximation Algorithms for the Knapsack and Sum of Subset Problemst by Oscar H. Ibarra and I;hul E. Kim Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455

Abstract

Given a positive integer M and n pairs of positive integers

(Equation Omitted)

maximize the sum Ed ipi subject to the constraints

(Equation Omitted)

This is the well known 0/1 knapsack problem. An algorithm is presented which finds for any

(Equation Omitted)

where P* is the desired optimal sum. Moreover, the algorithm runs in time

(Equation Omitted)

are functions depending only on s . Thus, for a fixed error, the algorithm has time complexity 4(nlogn) and space complexity 0(n). Hodificatioa of the algorithm for the general knapsack problem where the di's can be any non-negative integer results is a 0(u(e)n) computing time. A linear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that pi/ci is the same for all

(Equation Omitted)

Key Words: Knapsack problem, sum of subset; problem, polynomf.ally complete problem, polynomial time-bounded Turing machine, approximation algorithm.

t This research was supported by the National Science Foundation Grant GJ-35614.

1. Introduction

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 20

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

A well known combinatorial problem that finds applications to capital bud-geting problems [B], loading problems, and solutions of large optimization problems is the knapsack problem. A simplified version, known as the 0/1 knapsack problem, can be stated as follows: Given a positive integer M and a multiaetl Q consisting of n pairs of positive integers

(Equation Omitted)

maximize the sum Edipi subject to the constraints

(Equation Omitted)

may be interpreted as the profit and weight associated with the i-th-object which can be put into a knapsack whose total weight capacity is M . Throughout the paper we shall arsaumo, with no loss of generality, that each ci < M. Several algorithms have been introduced forsolving the 0/1 knapsack problem, i.e., for,fin;3lag the optimal sum, f* (see, e.g., [2,a,6,7,a;.)* However, all of these algorithms have a worst case computing time which is , exponential in n (the somber of pairs in Thus, these algorithms are only practical. for small values of n . It would indeed be interacting to develop a polynomial time algorithm to solve the knapsack problem. However, it is generally believed that such an...