Topics in the Design and Analysis of Combinatorial Algorithms

Abstract

This thesis presents topics in the analysis and design of Combinatorial Algorithms. The second chapter introduces a technique for obtaining more precise closed form solutions of recurrence relations defined by minimization and maximization operators. Since such recurrences arise quite frequently in the analysis of the complexity and performance of algorithms it is important to develop techniques for their solution. The technique used is next applied to give precise solutions for the cost of optimal "lopsided trees." These trees model a number of problems arising in practise.

The next chapter deals with self-organizing data structures. These data structures allow efficient access of the data elements when the elements are accessed according to an unknown probability distribution. We show that rearrangment rules from a certain general class can be modified so as to reduce the number of data moves, while leaving unchanged the asymptotic behaviour of the mean and variance of the cost of a data access. Since a data movement usually costs at least as much as a single probe the modified rule eventually leads to savings in total cost (the sum of the costs of comparisons and data movements).

In the third chapter we show that a certain problem, called the Linear Net Routing Problem, which arises in VLSI applications is NP-Complete. We also describe an heuristic for this problem which was proposed by K. J. Supowit.

In the last chapter an algorithm for optimization convex quadratic forms over polytopes is described. This is an extension of the linear programming algorithm presented by Karmarkar and is joint work with P. Vaidya. We also use the linear programming algorithm to present an algorithm for multi-commodity flows.