MATH 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, acelis@emory.edu |
| Date: 2015-04-02 at 1:00PM |
| Venue: MSC E408 |
| Download Flyer |
| Abstract: 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