Topics in the Design and Analysis of Combinatorial Algorithms
Kapoor, Sanjiv
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69561
Description
Title
Topics in the Design and Analysis of Combinatorial Algorithms
Author(s)
Kapoor, Sanjiv
Issue Date
1986
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
