A Stochastic Model for Networks that Arise from Conference Scheduling Problems Pubblico
Celis, Andres (2015)
Published
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:
1. 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.
2. 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 Ω (T1/4/(log T)3/4). We also argue that the expected clique and chromatic numbers of our model are upper bounded by O(T1/4) and O(T2/5), respectively.
Table of Contents
1 Introduction...1
2 Graph Coloring and Existing Graph Models...3
2.1 Graph Coloring...3
2.2 Erdos-Rényi Model...4
2.3 Barabási-Albert Model...5
2.4 Evolving Copying Model...5
2.5 Coloring Algorithms...6
2.5.1 Greedy...6
2.5.2 DSATUR...7
2.5.3 RLF...7
2.5.4 Ex-DSATUR...8
3 Haws Model...9
3.1 General Description...9
3.2 Construction Process and Choosing Edges...11
4 Analysis of Haws Model and Future Work...14
4.1 Experimental Results...14
4.1.1 Degree Distribution Results...14
4.1.2 Clique and Chromatic Number Results...18
4.2 Analysis...30
4.2.1 The Triangle Model...30
4.2.2 Degree Estimates...32
4.2.3 Lower Bounds...32
4.2.4 Upper Bounds...33
4.3 Summary and Future Work...34
Appendix...36
5.1 Haws Model Graph Generator...36
5.2 Usage...40
Bibliography...43
About this Master's Thesis
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Parola chiave | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
A Stochastic Model for Networks that Arise from Conference Scheduling Problems () | 2018-08-28 10:40:51 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|