Leveraging geometric approaches in data analytics and optimization
Reyhaneh Mohammadi · 2022
Geometric optimization is mainly focused on problems dealing with allocating a finite set ofresources to fulfill the demand that is dispersed over a geographical region. Exploiting the geometric characteristics of the problem such as shape, contiguity, and convexity, and integrating them into the optimization techniques, often helps to solve such problems more efficiently. This dissertation studies three different problems in this direction. The goal of the research is to find efficient solutions for some geometric optimization problems that are proved to be NP-hard. In the first project, we study a space partitioning problem and deal with finding an efficient partitioning scheme for generating treemaps that is a widely used tool in the data visualization field. A treemap takes a weighted tree structure and visualizes its leaves in a nested planar geometric shape such that it forms a partitioning of space with areas of sub-regions proportional to the weight of the nodes in the tree. We present an optimization model and five new algorithms including two divide and conquer approaches and three spiral treemap algorithms for this problem. Our optimization model generates superior treemaps that could serve as a benchmark for comparing the quality of computationally more efficient algorithms. We also presented an approximation algorithm with factor around 1.2 for this problem. In the second project, we study the k-medians problem, a well-known location optimization problem, in which the objective is to establish k facilities in a way to minimize the total (average) distance from each demand point to its nearest facility. Here, we assume that the demand points form a continuum in a polygonal region. This problem is called the continuous k-medians problem. We developed two approximation algorithms for this problem with approximation factors less than 1.81 and 1.64. We showed that the average performance is far better and within 1.2 factor of the optimal solution, which we further improved slightly by applying a modification in the algorithms. In the third project, we study a delivery routing problem where we combine trucks and drones to serve all demand points in a coordinated system. In this problem, the truck not only contributes to the actual delivery operation but also is used as a drone dispatcher and the battery charger. We developed an algorithm based on Variable Neighborhood Search for this problem.--Author's abstract