Matching and Scheduling Algorithms on Large Scale Dynamic Graphs

Abstract

The research for this thesis was conducted at Progressive Planning, an online multi-project management tool. For Progressive Planning, the precedence graph determines a partial ordering of the execution of jobs in each project. This graph is large, and data changes frequently. Edges, vertices and weights can be added, removed or updated. In this setting, I study heuristic algorithms both for scheduling tasks of projects in Progressive Planning, and for the maximum weighted matching problem. I developed an algorithm to quickly schedule a large number of jobs, using a simple, but effective decision measure. Furthermore, I reduce the problem size by dynamically maintaining connected components. For the maximum weighted matching problem, I developed a simple algorithm that maintains a half-approximation on incremental, linear graphs. This algorithm can also maintain a matching of unverified quality on generic incremental graphs. Lastly, I show that this algorithm is well suited for parallel computing.