Parameterized Approaches for Large-Scale Optimization Problems
MetadataShow full item record
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.
node-weighted Steiner tree
maximum-weight connected subgraph
exponential time hypothesis
Buchanan, Austin Loyd (2015). Parameterized Approaches for Large-Scale Optimization Problems. Doctoral dissertation, Texas A & M University. Available electronically from