Theses and Dissertations Collection

This research focuses on doing optimizations for hard problems in geometry and networks. Hard problems take exponential time for their computation. We focus on optimizing the cost. Our problems come in two spaces - metric space and network space. The cost in a metric space is often the distance whereas the cost in a network space is often in dynamic edge weights.

In a metric space, the properties of distance are preserved. We include techniques for optimizing different hard problems in metric space related to graphs and geometry. We propose efficient optimizations to reduce the time for solving hard problems in metric space by using approximation algorithms and sequence alignment algorithms.

In network space, distance properties often cannot be applied. Consider vehicle traffic networks. Suppose a vehicle has to travel from location A to location B. A straight line path between A and B may cut through a building. Therefore, the vehicle can travel from A to B using only the roads available between A and B. The interconnection of roads can be visualized as a set of edges and nodes in a network space. The roads are considered edges, and the intersections are considered nodes in network space. The cost of an edge is dynamic in that it depends on many variables including the amount of traffic on the edge. Optimizations in network space are complex and take exponential time. On top of that, the road traffic simulations can be very slow and leave out real world considerations in traffic flow. Our work proposes efficient traffic simulation optimizations in network space using a meso-level simulator, and a machine learning algorithm, to perform road traffic simulations efficiently and more realistically.