31
Mar
Speaker: Abraham Flaxman
Time: Monday 10:30-11:30 AM
Place: Wean 5320
Title: Average-case analysis for combinatorial problems
Abstract:
This thesis considers the average case analysis of algorithms, focusing primarially on NP-hard combinatorial optimization problems. It contains a catalog of distributions frequently used in average-case analysis and collection of mathematical tools that have proven useful in studying these distributions. The bulk of the thesis consists of case-studies in average-case analysis of algorithms, where algorithms for 3-SAT, Subset Sum, Strong Connectivity, Stochastic Minimum Spanning Tree, and Uncapacitated Facility Location are analyzed on random instances.
