dc.contributor.advisor | Butenko, Sergiy | |
dc.creator | Buchanan, Austin Loyd | |
dc.date.accessioned | 2015-10-29T19:44:37Z | |
dc.date.available | 2017-08-01T05:37:39Z | |
dc.date.created | 2015-08 | |
dc.date.issued | 2015-07-10 | |
dc.date.submitted | August 2015 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/155568 | |
dc.description.abstract | In this dissertation, we study challenging discrete optimization problems from the perspective of parameterized complexity. The usefulness of this type of analysis is twofold. First, it can lead to efficient algorithms for large-scale problem instances. Second, the analysis can provide a rigorous explanation for why challenging problems might appear relatively easy in practice. We illustrate the approach on several different problems, including: the maximum clique problem in sparse graphs; 0-1 programs with many conflicts; and the node-weighted Steiner tree problem with few terminal nodes. We also study polyhedral counterparts to fixed-parameter tractable
algorithms. Specifically, we provide fixed-parameter tractable extended formulations for independent set in tree-like graphs and for cardinality-constrained vertex covers. | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.subject | parameterized complexity | en |
dc.subject | integer programming | en |
dc.subject | extended formulations | en |
dc.subject | fixed-parameter tractable | en |
dc.subject | combinatorial optimization | en |
dc.subject | Steiner tree | en |
dc.subject | node-weighted Steiner tree | en |
dc.subject | maximum-weight connected subgraph | en |
dc.subject | vertex cover | en |
dc.subject | independent set | en |
dc.subject | maximum clique | en |
dc.subject | degeneracy | en |
dc.subject | conflict graph | en |
dc.subject | 0-1 program | en |
dc.subject | treewidth | en |
dc.subject | independence system | en |
dc.subject | extension complexity | en |
dc.subject | exponential time hypothesis | en |
dc.subject | cardinality constraint | en |
dc.subject | polyhedra | en |
dc.subject | polytope | en |
dc.subject | algorithm | en |
dc.subject | connectivity | en |
dc.title | Parameterized Approaches for Large-Scale Optimization Problems | en |
dc.type | Thesis | en |
thesis.degree.department | Industrial and Systems Engineering | en |
thesis.degree.discipline | Industrial Engineering | en |
thesis.degree.grantor | Texas A & M University | en |
thesis.degree.name | Doctor of Philosophy | en |
thesis.degree.level | Doctoral | en |
dc.contributor.committeeMember | Chen, Jianer | |
dc.contributor.committeeMember | Kianfar, Kiavash | |
dc.contributor.committeeMember | Moreno-Centeno, Erick | |
dc.type.material | text | en |
dc.date.updated | 2015-10-29T19:44:37Z | |
local.embargo.terms | 2017-08-01 | |
local.etdauthor.orcid | 0000-0002-4080-4017 | |