Committee Chair

Weerasena, Lakmali

Committee Member

Ebiefung, Aniekan; Saleh, Ossama; Gunasekera, Sumith

Department

Dept. of Mathematics

College

College of Arts and Sciences

Publisher

University of Tennessee at Chattanooga

Place of Publication

Chattanooga (Tenn.)

Abstract

The goal of classical KP, is to find a subset of items whose total weight does not exceed the knapsack capacity, and whose profit is a maximum. In the robust KP the goal is to find a subset of items whose total weight does not exceed the knapsack capacity, and remains near maximum for the worst scenario. Solving the robust KP exactly is difficult due to this data uncertainty and combinatorial structure of the problem. In this research, a polynomial-time algorithm is proposed to approximately obtain a near optimal solution for the robust KP with a provable quality. The quality is described by an error term and it is derived for the proposed algorithm. It is shown that the error depends on the characteristics of the problem. We verify the accuracy of the algorithm theoretically and computationally. It is shown that the error depends on the characteristics of the problem. We verify the accuracy of the algorithm theoretically and computationally.

Acknowledgments

SIMCenter-Center of Excellence in Applied Computational Science and Engineering at University of Tennessee Chattanooga

Degree

M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.

Date

5-2019

Subject

Mathematical optimization; Knapsack problem (Mathematics)

Keyword

Knapsack Problem; Robust optimization; Discrete optimization

Document Type

Masters theses

DCMI Type

Text

Extent

xiii, 68 leaves

Language

English

Rights

https://rightsstatements.org/page/InC/1.0/?language=en

License

http://creativecommons.org/licenses/by-sa/3.0/

Download

Share

COinS