{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/16477"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/16477","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"New approximation methods for solving binary quadratic programming problem","abstract":"In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\\epsilon) approximation ratio to the reformulated clustering problem.","abstract_html":"In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\\epsilon) approximation ratio to the reformulated clustering problem.","abstract_has_math":false,"creators":["Yang, Rui"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Systems & Entrepreneurial Engr","degree_department":null,"school":null,"contributors":["Peng, Jiming"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-06-22T19:37:18Z","date_published":"2010-06-22T19:37:18Z","updated_at":"2026-07-22T22:25:09Z","subjects":["Semidefinite Programming Relaxation","Binary Quadratic Problem","Approximation Algorithm","Core-set Technique"],"languages":["en"],"rights":["Copyright 2010 Rui Yang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/16477","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Peng, Jiming"]},{"key":"dc:creator","label":"Author","values":["Yang, Rui"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-06-22T19:37:18Z","2010-5"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Systems & Entrepreneurial Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Semidefinite Programming Relaxation","Binary Quadratic Problem","Approximation Algorithm","Core-set Technique"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Rui Yang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/16477"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\\epsilon) approximation ratio to the reformulated clustering problem.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-04-30T13:23:33Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Yang_Rui.rar: 60154 bytes, checksum: b7d21e9fba2186223643a3b9fc205759 (MD5) Yang_Rui.pdf: 330952 bytes, checksum: 6675179f8b6ff0e37bee0a8a78c9bd96 (MD5)","Made available in DSpace on 2010-06-22T19:37:18Z (GMT). No. of bitstreams: 4 Yang_Rui.pdf: 330952 bytes, checksum: 6675179f8b6ff0e37bee0a8a78c9bd96 (MD5) Yang_Rui.rar: 60154 bytes, checksum: b7d21e9fba2186223643a3b9fc205759 (MD5) 1_Yang_Rui.pdf: 332870 bytes, checksum: 496b0d25f203b06595392f0f76f86e16 (MD5) license.txt: 4058 bytes, checksum: 4c5ff90411c1b6bf568b7dc4a7c29bac (MD5)"]},{"key":"dc:title","label":"Title","values":["New approximation methods for solving binary quadratic programming problem"]}]}],"canonical_facts":{"dc:contributor":["Peng, Jiming"],"dc:creator":["Yang, Rui"],"dc:date":["2010-06-22T19:37:18Z","2010-5"],"dc:description":["In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\\epsilon) approximation ratio to the reformulated clustering problem.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-04-30T13:23:33Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Yang_Rui.rar: 60154 bytes, checksum: b7d21e9fba2186223643a3b9fc205759 (MD5) Yang_Rui.pdf: 330952 bytes, checksum: 6675179f8b6ff0e37bee0a8a78c9bd96 (MD5)","Made available in DSpace on 2010-06-22T19:37:18Z (GMT). No. of bitstreams: 4 Yang_Rui.pdf: 330952 bytes, checksum: 6675179f8b6ff0e37bee0a8a78c9bd96 (MD5) Yang_Rui.rar: 60154 bytes, checksum: b7d21e9fba2186223643a3b9fc205759 (MD5) 1_Yang_Rui.pdf: 332870 bytes, checksum: 496b0d25f203b06595392f0f76f86e16 (MD5) license.txt: 4058 bytes, checksum: 4c5ff90411c1b6bf568b7dc4a7c29bac (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/16477"],"dc:language":["en"],"dc:rights":["Copyright 2010 Rui Yang"],"dc:subject":["Semidefinite Programming Relaxation","Binary Quadratic Problem","Approximation Algorithm","Core-set Technique"],"dc:title":["New approximation methods for solving binary quadratic programming problem"],"thesis:degree_discipline":["Systems & Entrepreneurial Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:09Z"}