-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
			 Wednesday May 15, 1996
                                       
				2:00 pm
                                       
		       (Coffee served at 1:30 pm)

			 Seminar Room / MCS 135

-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------

	       Optimization Algorithms for Large Networks

			    Andrew Goldberg
		      NEC Research Institute, Inc.
				    

    As computer memory size increases and applications get more
    sophisticated, larger problems come up in practice. The algorithm
    running time is usually superlinear in the problem size, so big problems
    require more time even though computers get faster. This makes efficient
    algorithms more important.
    
    For network optimization problems, significant progress has been made on
    designing theoretically efficient algorithms.  Although good theoretical
    bounds do not guarantee good practical performance, some of the recent
    algorithms are practical, outperforming previous methods by a
    significant margin.
    
    We review two techniques for designing network optimization algorithms,
    the push-relabel method and cost scaling.  We consider applications of
    these techniques to several important problems, including maximum flows,
    minimum cuts, and minimum-cost flows.  We give discuss additional
    techniques needed to obtain practical implementations of these methods
    and illustrate the importance of these techniques by experimental data.
    
    One of the main distinguishing characteristics of this work is
    interaction between design, theoretical analysis, and experimental
    evaluation of algorithms.
    
-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------