MathCS Seminar

Title: A Stochastic Model for Networks at Arise from Conference Scheduling Problems
Defense: Master's Thesis
Speaker: Andres Celis of Emory University
Contact: Andres Celis,
Date: 2015-04-02 at 1:00PM
Venue: E408
Download Flyer
A conference scheduling problem may be viewed as an undirected graph whose vertices correspond to the events of the conference, and whose edges correspond to constraints that prohibit two events from being scheduled at the same time. In this thesis we propose and analyze a new random graph model inspired by a series of experimental observations on datasets from the industry, as well as conversations with a conference scheduler.\\ \\ Our models differs from existing random graph models in the following: \begin{enumerate} \item We find that graph models with independently chosen edges do not result in degree distributions found in conference scheduling problems. Thus our model's edges are statistically dependent on each other. \item Our model introduces new vertices into the graph as time evolves. The existing models that do this have small, bounded clique and chromatic numbers and are trivial to color, which is not an accurate representation of scheduling problems. We show that the expected clique number of our model has a lower bound of $\Omega(T^{1/4}/(\log T)^{3/4})$. We also argue that the expected clique and chromatic numbers of our model are upper bounded by $O(T^{1/4})$ and $O(T^{2/5})$, respectively. \end{enumerate}

See All Seminars