Quadratic Bottleneck Problems: Algorithms, complexity and related topics.

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.