{"id":{"repo_id":"utc","oai_identifier":"oai:scholar.utc.edu:theses-1746"},"canonical_url":"https://search.dev.ndltd.org/etd/utc/oai:scholar.utc.edu:theses-1746","repository":{"repo_id":"utc","name":"University of Tennessee - Chattanooga","base_url":"https://scholar.utc.edu/do/oai/"},"display":{"title":"Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Smith, Blake"],"institution":"University of Tennessee at Chattanooga","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Weerasena, Lakmali","Ebiefung, Aniekan; Saleh, Ossama; Gunasekera, Sumith","College of Arts and Sciences"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T05:46:51Z","subjects":["Mathematical optimization","Knapsack problem (Mathematics)"],"languages":["English","eng"],"rights":[],"rights_urls":["https://rightsstatements.org/page/InC/1.0/?language=en"],"identifier_entries":[]},"links":{"outbound_url":"https://scholar.utc.edu/theses/598","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Weerasena, Lakmali","Ebiefung, Aniekan; Saleh, Ossama; Gunasekera, Sumith","College of Arts and Sciences"]},{"key":"dc:creator","label":"Author","values":["Smith, Blake"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-05-01T07:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["University of Tennessee at Chattanooga","Chattanooga (Tenn.)"]},{"key":"dc:relation","label":"Dc Relation","values":["Masters Theses and Doctoral Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["Masters theses","Text"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematical optimization","Knapsack problem (Mathematics)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://rightsstatements.org/page/InC/1.0/?language=en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholar.utc.edu/theses/598"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Dept. of Mathematics","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."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem"]}]}],"canonical_facts":{"dc:contributor":["Weerasena, Lakmali","Ebiefung, Aniekan; Saleh, Ossama; Gunasekera, Sumith","College of Arts and Sciences"],"dc:creator":["Smith, Blake"],"dc:date":["2019-05-01T07:00:00Z"],"dc:description":["Dept. of Mathematics","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."],"dc:description.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."],"dc:identifier":["https://scholar.utc.edu/theses/598"],"dc:language":["English","eng"],"dc:publisher":["University of Tennessee at Chattanooga","Chattanooga (Tenn.)"],"dc:relation":["Masters Theses and Doctoral Dissertations"],"dc:rights":["https://rightsstatements.org/page/InC/1.0/?language=en"],"dc:subject":["Mathematical optimization","Knapsack problem (Mathematics)"],"dc:title":["Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem"],"dc:type":["Masters theses","Text"]},"updated_at":"2026-07-24T05:46:51Z"}