Parameterized Approaches for Large-Scale Optimization Problems
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.
Subject
parameterized complexityinteger programming
extended formulations
fixed-parameter tractable
combinatorial optimization
Steiner tree
node-weighted Steiner tree
maximum-weight connected subgraph
vertex cover
independent set
maximum clique
degeneracy
conflict graph
0-1 program
treewidth
independence system
extension complexity
exponential time hypothesis
cardinality constraint
polyhedra
polytope
algorithm
connectivity
Citation
Buchanan, Austin Loyd (2015). Parameterized Approaches for Large-Scale Optimization Problems. Doctoral dissertation, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /155568.