{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121437"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121437","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Combining combinatorial and LP-based methods for better and faster approximation algorithms","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled &#x27;Open Access&#x27;. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_has_math":false,"creators":["Torres, Manuel R"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chekuri, Chandra","Har-Peled, Sariel","Chandrasekaran, Karthekeyan","Mishra, Nina"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Theoretical Computer Science","Algorithms","Approximation Algorithms","Combinatorial Optimization","Linear Programming","Dense Subgraph Discovery"],"languages":["en","eng"],"rights":["Copyright 2023 Manuel Torres"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121437","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chekuri, Chandra","Har-Peled, Sariel","Chandrasekaran, Karthekeyan","Mishra, Nina"]},{"key":"dc:creator","label":"Author","values":["Torres, Manuel R"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-06-29"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["Theoretical Computer Science","Algorithms","Approximation Algorithms","Combinatorial Optimization","Linear Programming","Dense Subgraph Discovery"]}]},{"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 Manuel Torres"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121437"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Manuel Torres, accepted the attached license on 2023-06-28 at 11:20.","The student, Manuel Torres, submitted this Dissertation for approval on 2023-06-28 at 16:11.","This Dissertation was approved for publication on 2023-06-29 at 14:38.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19472 on 2023-12-04 at 17:00:16","We study several combinatorial optimization problems and develop approximation algorithms to solve them. Considering the rapid growth of data set sizes, our focus is the design of fast approximation algorithms. Many of the approximation algorithms we develop are based on linear programming (LP) relaxations. We design fast algorithms for both solving and rounding LPs. Our fast LP solvers build upon recent improvements used to solve LPs efficiently, such as those based on the multiplicative weight updates framework. The first problem we consider is the problem of packing integer programs (PIPs), which are problems of the form $\\max\\{\\langle c, x \\rangle : x \\in \\{0,1\\}^n, Ax \\le b\\}$ where A, b, and c are all nonnegative. Let $W = \\max_{i,j : A_{i,j} > 0} \\frac{b_i}{A_{i,j}}$ be the width of the given PIP. We present randomized algorithms, obtaining approximations in terms of the maximum column sum $\\Delta_1$ of A when W > 1, and we show that it is NP-hard to approximate PIPs solely in terms of $\\Delta_1$ when W = 1. The second problem we consider is the bounded degree minimum spanning tree problem (BD-MST), an NP-hard variant of the minimum spanning tree problem where we also want to satisfy degree constraints. We design a near-linear time approximation algorithm for BD-MST by speeding up algorithms for solving the natural LP relaxation and for a known dependent randomized rounding technique called swap rounding. We extend these results to a generalization known as the crossing spanning tree problem. The third problem we consider is the densest subgraph problem (DSG). We make three main contributions. The first is a fast $(1-\\epsilon)$-approximation based on maximum flow. The second result resolves a conjecture from previous work showing that an iterative greedy peeling algorithm Greedy++ in fact converges to a near-optimal solution. For the third contribution, using the lens of supermodularity, we unify and generalize many existing notions of density in the literature, referring to this problem as the densest supermodular subset problem (DSS). This supermodular perspective facilitated the convergence proof of Greedy++. We give a simple peeling algorithm for DSS and prove the convergence of an iterative generalization similar to Greedy++. Finally, we consider the p-mean densest subgraph problem (p-mean DSG) where p is a parameter defining the objective, which generalizes both DSG and the maximum k-core. For $p \\ge 1$, the objective is supermodular and thus a special case of DSS. We show how to speed up the running time of the simple peeling algorithm for p-mean DSG. For p < 1, we show that the problem is NP-hard and develop approximation algorithms. We supplement our theoretical results with empirical evaluation of our algorithms on real-world graphs."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Combining combinatorial and LP-based methods for better and faster approximation algorithms"]}]}],"canonical_facts":{"dc:contributor":["Chekuri, Chandra","Har-Peled, Sariel","Chandrasekaran, Karthekeyan","Mishra, Nina"],"dc:creator":["Torres, Manuel R"],"dc:date":["2023-08","2023-06-29"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Manuel Torres, accepted the attached license on 2023-06-28 at 11:20.","The student, Manuel Torres, submitted this Dissertation for approval on 2023-06-28 at 16:11.","This Dissertation was approved for publication on 2023-06-29 at 14:38.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19472 on 2023-12-04 at 17:00:16","We study several combinatorial optimization problems and develop approximation algorithms to solve them. Considering the rapid growth of data set sizes, our focus is the design of fast approximation algorithms. Many of the approximation algorithms we develop are based on linear programming (LP) relaxations. We design fast algorithms for both solving and rounding LPs. Our fast LP solvers build upon recent improvements used to solve LPs efficiently, such as those based on the multiplicative weight updates framework. The first problem we consider is the problem of packing integer programs (PIPs), which are problems of the form $\\max\\{\\langle c, x \\rangle : x \\in \\{0,1\\}^n, Ax \\le b\\}$ where A, b, and c are all nonnegative. Let $W = \\max_{i,j : A_{i,j} > 0} \\frac{b_i}{A_{i,j}}$ be the width of the given PIP. We present randomized algorithms, obtaining approximations in terms of the maximum column sum $\\Delta_1$ of A when W > 1, and we show that it is NP-hard to approximate PIPs solely in terms of $\\Delta_1$ when W = 1. The second problem we consider is the bounded degree minimum spanning tree problem (BD-MST), an NP-hard variant of the minimum spanning tree problem where we also want to satisfy degree constraints. We design a near-linear time approximation algorithm for BD-MST by speeding up algorithms for solving the natural LP relaxation and for a known dependent randomized rounding technique called swap rounding. We extend these results to a generalization known as the crossing spanning tree problem. The third problem we consider is the densest subgraph problem (DSG). We make three main contributions. The first is a fast $(1-\\epsilon)$-approximation based on maximum flow. The second result resolves a conjecture from previous work showing that an iterative greedy peeling algorithm Greedy++ in fact converges to a near-optimal solution. For the third contribution, using the lens of supermodularity, we unify and generalize many existing notions of density in the literature, referring to this problem as the densest supermodular subset problem (DSS). This supermodular perspective facilitated the convergence proof of Greedy++. We give a simple peeling algorithm for DSS and prove the convergence of an iterative generalization similar to Greedy++. Finally, we consider the p-mean densest subgraph problem (p-mean DSG) where p is a parameter defining the objective, which generalizes both DSG and the maximum k-core. For $p \\ge 1$, the objective is supermodular and thus a special case of DSS. We show how to speed up the running time of the simple peeling algorithm for p-mean DSG. For p < 1, we show that the problem is NP-hard and develop approximation algorithms. We supplement our theoretical results with empirical evaluation of our algorithms on real-world graphs."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121437"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Manuel Torres"],"dc:subject":["Theoretical Computer Science","Algorithms","Approximation Algorithms","Combinatorial Optimization","Linear Programming","Dense Subgraph Discovery"],"dc:title":["Combining combinatorial and LP-based methods for better and faster approximation algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"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"}