Hybrid Rounding Techniques for Knapsack Problems

Details Hybrid Rounding Techniques for Knapsack Problems Hybrid Rounding Techniques for Knapsack Problems

2003-05-02

arxiv.org/abs/cs/0305002v1

Discrete Applied Mathematics, 154:4 (2006) 640-649

Computer Science

Computational Complexity

19 LaTeX pages

Scientific paper

10.1016/j.dam.2005.08.004

We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and powerful ways of rounding. As an application of these techniques, we present a linear-storage Polynomial Time Approximation Scheme (PTAS) and a Fully Polynomial Time Approximation Scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds.

Affiliated with

Also associated with

No associations

Rating

Hybrid Rounding Techniques for Knapsack Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hybrid Rounding Techniques for Knapsack Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid Rounding Techniques for Knapsack Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-154551