Algortithms for the Min-Cut problem

Algorithms for the Min-Cut problem : The project will discuss the Min-Cut problem, and introduce some classical algorithms on it. One of the algorithms is a random algorithm developed by Karger. The fundamental idea of this algorithm is "edge contraction". The probability of a successful contraction algorithm is 2/n, and the algorithm's complexity is O(n^4 \log n), where n=|V(G)|. Based on the analysis of Karger's algorithm, an improved algorithm, Karger-Stein algorithm, will be introduced. The faster algorithm can find the Min-Cut within the probability larger than 2 \log 2 / \log n, thus the complexity of faster algorithm is O(n^2 \log n). The project will also show an example, whose simple graph has 200 vertices, to see the difference between Karger's algorithm and Karger-Stein's algorithm, coded in Python.

A Polynomial Approximation to the Matrix Permanent via Markov Chain Monte Carlo.: The permanent of a matrix has been studied for over two centuries and provides a generalization of problems in graph theory. Though an exact algorithm for computing the permanent is not possible unless P=NP, a recently discovered polynomial time algorithm approximation of the permanent for non-negative matrices is presented. This algorithm is derived by generalizing a previous method of sampling perfect matchings using a Markov Chain Monte Carlo method. Reductions of graph theoretic problems preserving the approximation result are also considered, providing polynomial time approximation algorithms for related questions.

Event Topic

Discrete Applied Math Seminar