-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
		      T H E S I S   D E F E N S E
                                       
			Wednesday April 12, 1995
                                       
				3:00 pm
		       (Coffee served at 2:30 pm)
                                       
			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------
	    PARALLEL AND RANDOMIZED APPROXIMATION ALGORITHMS
	    FOR MAXCLIQUE AND MAXCUT AND THEIR APPLICATIONS

			     Marcus Peinado
			   Boston University

  The work in this thesis lies at the confluence of several areas of
  computer science, most importantly, the analysis of randomized
  approximation algorithms for NP-hard problems, parallel computation, and
  combinatorial optimization. Many problems in computational physics,
  chemistry or biology can be concisely stated as NP-hard combinatorial
  optimization problems. This makes it possible to employ standard tools
  and methods of computer science to solve them. Firstly, the known
  methods for the design and analysis of algorithms can be used to find
  efficient algorithmic solutions. Recent advances in the design of
  approximation algorithms seem particularly promising in this
  respect. Secondly, modern massively parallel machines often can provide
  the processing power needed to solve problems of practical
  interest. Both of these points are addressed in this thesis.
  
  The first algorithm for the Maxclique problem with a non-trivial
  performance guarantee was published in 1990 by Boppana and
  Halldorsson. Its performance guarantee is still unmatched by any other
  algorithm. The first part of this thesis analyzes a randomized version
  of this algorithm. The result is a strong lower bound on its performance
  guarantee.  The theoretical analysis is complemented with an
  experimental evaluation of the algorithm. Efficient parallel versions of
  the algorithms are derived. Their implementations on the Connection
  Machine 5 are used to approximate very large instances of the Maxclique
  problem with up to 70.000 vertices.
  
  The second half of the thesis focuses on the Maxcut problem. A highly
  parallel algorithm which is based on the approximation algorithm by
  Goemans and Williamson is derived. The speedups of the parallel
  algorithm are analyzed and it is shown that linear speedup is achieved
  on a wide range of network architectures. Experiments are performed on
  several classes of benchmark problems. Finally, a concrete application
  of Maxcut in statistical physics is studied. A branch and bound
  algorithm for Maxcut which uses a positive semidefinite relaxation for
  the bound is derived. This algorithm is used to enumerate all ground
  states of 5x5x5 Ising spin glass systems. A number of quantities of
  physical interest are derived from the ground states.

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------