Quadratic Bottleneck Problems: Algorithms, complexity and related topics.

Resource type
Thesis type
(Thesis) Ph.D.
Date created
2011-10-20
Authors/Contributors
Abstract
In this thesis we study the quadratic bottleneck combinatorial optimization problem (QBCOP) which generalizes the well-known class of bottleneck problems. The solvability of QBCOP is linked to that of the linear combinatorial optimization problems with conflict constraints. Various properties and algorithms for these classes of problems are developed and special cases of spanning trees, knapsack type problems, and assignment variations are explored. These problems are shown to be strongly NP-hard even on very special graphs. We then identify polynomially solvable special cases and also develop heuristic algorithms. Experimental results are reported for all the heuristics we developed. As a by-product of our work, we have an approximation algorithm for the maximum edge clique partitioning problem, improving the best known performance ratio for the problem.
Document
Identifier
etd6889
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Attachment Size
etd6889_RZhang.pdf 2.76 MB