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- 2Approximation Algorithms
- 1Approximation Algorithm
- 1Approximation algorithms
- 1Coloring
- 1Column Generation
- 1Combinatorial Optimization
-
Fall 2024
In this thesis, we introduce a new problem called the Minimum Sum Coloring with Bundles. We are given an undirected graph and bundles which bundles are sets of nodes (not necessarily disjoint). The goal is to find a proper coloring of the graph with positive integers to minimize the weighted...
-
Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
DownloadFall 2022
In this study, we present an improved approximation algorithm for three related problems. In the Minimum Sum of Radii clustering problem (MSR), we aim to select k balls in a metric space to cover all points while minimizing the sum of the radii. In the Minimum Sum of Diameters clustering problem...
-
Solving the LP Relaxation of Distance-Constrained Vehicle Routing Problem Using Column Generation
DownloadFall 2020
The distance-constrained vehicle routing problem (DVRP) is one of the less studied variants of vehicle routing problems. Here, the objective is to deliver packages from a depot to clients with as few delivery vehicles as possible within a given time frame. In this thesis, we tackle larger...
-
Spring 2017
Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr,kb and connect each client...