Derandomization of dimensionality reduction and semidefinite programming based approximation algorithms.

摘要

The dissertation introduces new tools to derandomize algorithms. These tools find application in derandomizing most approximation algorithms that are based on semidefinite optimization. We also apply these tools to construct deterministic embeddings for dimensionality reduction. These techniques give new ways to approximate conditional probabilities with bounded error and ways to bound conditional probabilities with new pessimistic estimator functions. These ideas are more generally applicable and not limited to the problems that they are applied to here.; In applying some of these new ideas we give a fast deterministic algorithm for the Maximum cut problem. This algorithm gives the same approximation guarantee as that of Goemans and Williamson. Our result significantly improves on known deterministic algorithms for this problem both in time complexity and approximation factor. For the problem of dimensionality reduction we improve on the run time of known deterministic algorithms. For some varieties of dimensionality reduction our algorithms run in cubic time improving on known algorithms that run in very high order polynomial time.