{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/34612"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/34612","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"A multiscale approximation algorithm for the cardinality constrained knapsack problem","abstract":"I develop a multiscale approximation algorithm for the cardinality constrained knapsack problem. The algorithm consists of three steps: a rounding and reduction step where a hierarchical representation of the problem data ranging from coarse to fine is generated, a solution step where a coarse solution is computed, and a refinement step where the accuracy of the solution is improved by refining the problem representation. I demonstrate that the algorithm is fully polynomial with a runtime complexity that improves upon the previous best known fully polynomial approximation scheme. Through an extensive computational study, I show that the running times of the algorithm is less than or equal to that of a commercial integer programming package with little loss in solution accuracy.","abstract_html":"I develop a multiscale approximation algorithm for the cardinality constrained knapsack problem. The algorithm consists of three steps: a rounding and reduction step where a hierarchical representation of the problem data ranging from coarse to fine is generated, a solution step where a coarse solution is computed, and a refinement step where the accuracy of the solution is improved by refining the problem representation. I demonstrate that the algorithm is fully polynomial with a runtime complexity that improves upon the previous best known fully polynomial approximation scheme. Through an extensive computational study, I show that the running times of the algorithm is less than or equal to that of a commercial integer programming package with little loss in solution accuracy.","abstract_has_math":false,"creators":["Krishnan, Bharath Kumar"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering.","school":null,"contributors":[],"advisors":["George A. Kocur."],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006","date_published":"2006","updated_at":"2026-07-22T22:21:59Z","subjects":["Civil and Environmental Engineering."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/34612","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["George A. Kocur."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering."]},{"key":"dc:creator","label":"Author","values":["Krishnan, Bharath Kumar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-11-07T13:35:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-11-07T13:35:10Z"]},{"key":"dc:date.issued","label":"Date","values":["2006"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Civil and Environmental Engineering."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/34612"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2006.","Includes bibliographical references (leaves 83-86)."]},{"key":"dc:description.abstract","label":"Abstract","values":["I develop a multiscale approximation algorithm for the cardinality constrained knapsack problem. The algorithm consists of three steps: a rounding and reduction step where a hierarchical representation of the problem data ranging from coarse to fine is generated, a solution step where a coarse solution is computed, and a refinement step where the accuracy of the solution is improved by refining the problem representation. I demonstrate that the algorithm is fully polynomial with a runtime complexity that improves upon the previous best known fully polynomial approximation scheme. Through an extensive computational study, I show that the running times of the algorithm is less than or equal to that of a commercial integer programming package with little loss in solution accuracy."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A multiscale approximation algorithm for the cardinality constrained knapsack problem"]}]}],"canonical_facts":{"dc:contributor.advisor":["George A. Kocur."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering."],"dc:creator":["Krishnan, Bharath Kumar"],"dc:date.accessioned":["2006-11-07T13:35:10Z"],"dc:date.available":["2006-11-07T13:35:10Z"],"dc:date.issued":["2006"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2006.","Includes bibliographical references (leaves 83-86)."],"dc:description.abstract":["I develop a multiscale approximation algorithm for the cardinality constrained knapsack problem. The algorithm consists of three steps: a rounding and reduction step where a hierarchical representation of the problem data ranging from coarse to fine is generated, a solution step where a coarse solution is computed, and a refinement step where the accuracy of the solution is improved by refining the problem representation. I demonstrate that the algorithm is fully polynomial with a runtime complexity that improves upon the previous best known fully polynomial approximation scheme. Through an extensive computational study, I show that the running times of the algorithm is less than or equal to that of a commercial integer programming package with little loss in solution accuracy."],"dc:description.degree":["Ph.D."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/34612"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Civil and Environmental Engineering."],"dc:title":["A multiscale approximation algorithm for the cardinality constrained knapsack problem"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:59Z"}