This project focuses on the uses of randomization, with particular emphasis on graph algorithms. In particular, the problems to be ``tackled''(but not necessarily exactly solved) by the PI's randomized graphical optimization techniques include: (1) The maximum flow and minimum cut problems can be solved exactly, with the major objective being the design of faster, simpler and more practical algorithms for arriving at a correct answer; (2) Graph coloring and bisection, analysis of network reliability, and construction of low-cost high-connectivity networks, are extremely hard to solve exactly, with the major objective being to find efficient algorithms that give answers as close as possible to the elusive optimum. Implementation and testing of the algorithmic solutions is an integrated component of this project. The Integrated Educational Plan of this CAREER Grant includes the teaching, improvement and development of theoretical computer science courses, including: (1) Undergraduate algorithms course; (2) Undergraduate discrete mathematics course; (3) Graduate randomized algorithms course; (4) Undergraduate information retrieval and text databases.
