This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
Search
Skip to Search Results- 1Algorithm
- 1Approximation
- 1Approximation Algorithms
- 1Approximation algorithms, flow-shop scheduling, min-sum edge colouring
- 1Clustering
- 1PTAS
-
A Polynomial-Time Approximation Scheme for Traveling Salesman Problem with Neighborhoods Over Parallel Line Segments of Similar Length
DownloadFall 2024
In this thesis, we consider the Traveling Salesman Problem with Neighborhoods (TSPN) on the Euclidean plane, and present a Polynomial-Time Approximation Scheme (PTAS) when the neighborhoods are parallel line segments with lengths between [1, λ] for any constant value λ.In TSPN (which generalizes...
-
Spring 2023
In this thesis, we present Approximation Schemes for the Min Sum k Clustering problem on a number of classes of graph metrics. In Min Sum k Clustering problem introduced by Sahni and Gonzalez [22] in 1976, given a graph G(V, E) with metric edge costs and parameter k, we are asked to partition V...
-
Fall 2017
In this thesis, we consider scheduling problems in which jobs need to be processed through a (shared) network of machines according to their given paths. Formally, we are given a graph $G(V, E)$ where the edges $E$ represent the machines. We are also given a set of jobs $J$ and a path of edges...