{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120506"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120506","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"GPU-accelerated solutions for higher-order assignment and graph partition problems","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","abstract_has_math":false,"creators":["Vadrevu, Samhita"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh","Sreenivas, Ramavarapu","Etesami, Rasoul","Patel, Sanjay"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Multi-dimensional Assignment","Quadratic Assignment","Clique-partitioning","High Performance Computing (HPC)","Graphics Processing Units (GPU)","Compute Unified Device Architecture (CUDA)"],"languages":["en","eng"],"rights":["Copyright 2023 Samhita Vadrevu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120506","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh","Sreenivas, Ramavarapu","Etesami, Rasoul","Patel, Sanjay"]},{"key":"dc:creator","label":"Author","values":["Vadrevu, Samhita"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-04-17"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Multi-dimensional Assignment","Quadratic Assignment","Clique-partitioning","High Performance Computing (HPC)","Graphics Processing Units (GPU)","Compute Unified Device Architecture (CUDA)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Samhita Vadrevu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120506"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","The student, Samhita Vadrevu, accepted the attached license on 2023-04-07 at 18:19.","The student, Samhita Vadrevu, submitted this Dissertation for approval on 2023-04-07 at 19:45.","This Dissertation was approved for publication on 2023-04-17 at 16:02.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18933 on 2023-09-01 at 17:20:22","Applications of integer programming models are wide-spread, ranging from management (resource allocation, scheduling, facility location) to scientific applications (molecular biology, high-energy physics) [139]. However, a majority of these problems are NP-Hard and exact algorithms are not scalable. In this dissertation, an efficient and scalable framework is proposed to solve a class of integer programs, and is demonstrated using three prominent real-world applications. These problems are: (1) Multi-Target Tracking application formulated as the Multi-dimensional Assignment Problem (MAP), (2) facility location as the Quadratic Assignment Problem (QAP), and (3) the entity resolution problem formulated as a Clique Partitioning Problem (CPP). Firstly, a dual-ascent-based technique is proposed to solve MAP near-optimally. It is accompanied by a gap closure scheme to find provably optimal solutions. This algorithm can handle significantly large problems of up to 25 billion variables. Secondly, the QAP is approached from a maximum entropy perspective. A Sinkhorn algorithm is employed to find strong lower bounds to the linearized QAP and is equipped to handle problems of size 50 with memory complexity O(N6), translating to 15 billion edges. Lastly, a two-phase approach is proposed to solve the clique partitioning problem, where the first phase is to find maximal cliques in the graph, and the second phase is translated into a generalized set packing model. A novel formulation is proposed as a superior alternative to the traditional set-packing formulation in terms of memory efficiency. It is solved approximately using a GPU-accelerated and scalable heuristic and integrated with an exact parallel branch-and-bound scheme, providing provable optimal solutions."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["GPU-accelerated solutions for higher-order assignment and graph partition problems"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh","Sreenivas, Ramavarapu","Etesami, Rasoul","Patel, Sanjay"],"dc:creator":["Vadrevu, Samhita"],"dc:date":["2023-05","2023-04-17"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","The student, Samhita Vadrevu, accepted the attached license on 2023-04-07 at 18:19.","The student, Samhita Vadrevu, submitted this Dissertation for approval on 2023-04-07 at 19:45.","This Dissertation was approved for publication on 2023-04-17 at 16:02.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18933 on 2023-09-01 at 17:20:22","Applications of integer programming models are wide-spread, ranging from management (resource allocation, scheduling, facility location) to scientific applications (molecular biology, high-energy physics) [139]. However, a majority of these problems are NP-Hard and exact algorithms are not scalable. In this dissertation, an efficient and scalable framework is proposed to solve a class of integer programs, and is demonstrated using three prominent real-world applications. These problems are: (1) Multi-Target Tracking application formulated as the Multi-dimensional Assignment Problem (MAP), (2) facility location as the Quadratic Assignment Problem (QAP), and (3) the entity resolution problem formulated as a Clique Partitioning Problem (CPP). Firstly, a dual-ascent-based technique is proposed to solve MAP near-optimally. It is accompanied by a gap closure scheme to find provably optimal solutions. This algorithm can handle significantly large problems of up to 25 billion variables. Secondly, the QAP is approached from a maximum entropy perspective. A Sinkhorn algorithm is employed to find strong lower bounds to the linearized QAP and is equipped to handle problems of size 50 with memory complexity O(N6), translating to 15 billion edges. Lastly, a two-phase approach is proposed to solve the clique partitioning problem, where the first phase is to find maximal cliques in the graph, and the second phase is translated into a generalized set packing model. A novel formulation is proposed as a superior alternative to the traditional set-packing formulation in terms of memory efficiency. It is solved approximately using a GPU-accelerated and scalable heuristic and integrated with an exact parallel branch-and-bound scheme, providing provable optimal solutions."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120506"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Samhita Vadrevu"],"dc:subject":["Multi-dimensional Assignment","Quadratic Assignment","Clique-partitioning","High Performance Computing (HPC)","Graphics Processing Units (GPU)","Compute Unified Device Architecture (CUDA)"],"dc:title":["GPU-accelerated solutions for higher-order assignment and graph partition problems"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}