Type of Talk: ACT Seminar

Speaker Name: N

ayantara Bhatnagar

Speaker Affiliation: Georgia Tech

Date:

October 17 2005

Start Time: 1:00p.m.

Location: TAY 3.128 -
East wall (chalkboard)

Host: Adam Klivans

Talk Title: Rand

omly Generating Bipartite Graphs with a Prescribed Degree Sequence

T

alk Abstract:
We present an algorithm to generate a random labeled bipar

tite
graph with a given degree sequence. Previously the only algorithm

known for this problem was via reduction to approximating the permanent
which causes a quadratic increase in the size of the instance. We prove a
combinatorial lemma that allows us to bypass this reduction and define a s

imulated annealing algorithm.

Simulated annealing is a heuristic use

d in combinatorial optimization
where the algorithm is started at a high
temperature where
it is easy to obtain an optimal instance. The temper

ature is then
slowly cooled until we obtain the desired optimum at low

temperature. Our annealing algorithm is inspired by the annealing scheme us

ed by Jerrum Sinclair and Vigoda for computing the permanent. Our approach
can be generalized to generating subgraphs with a prescribed degree sequen

ce of a given bipartite graph and
this includes the permanent as a spec

ial case.

This is joint work with Ivona Bezakova and Eric Vigoda.