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- 10Approximation Algorithms
- 2Scheduling
- 1Algorithms
- 1Approximation
- 1Coloring
- 1Combinatorial Optimization
- 1Darbouy, Seyed Parsa
- 1Friggstad, Zachary
- 1Ghaseminia, Benyamin
- 1Hyatt-Denesik, Dylan V
- 1Jamshidian, Mahya
- 1Jorati, Amin
-
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...
-
Fall 2019
Scheduling problems are problems in which jobs are assigned to machines at particular times. A common objective of scheduling is to schedule as many jobs before their deadline as possible, called Throughput Maximization. In this thesis, we provide algorithms for various...
-
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...
-
Fall 2020
Scheduling problems are problems to assign jobs to machines at particular times while trying to optimize some objective function. In this work, we study one such problem, called Generalized Path Scheduling (GPS) problem, in which the machines form a path and each job is assigned a subpath of...
-
Approximation Algorithms for Single-Minded Pricing and Unique Coverage on Graphs and Geometric Objects
DownloadSpring 2015
We study the Single-Minded Pricing, Unique Coverage, and Uniform-Budget Single-Minded Pricing problems on graphs and on geometric objects. In Single Minded Pricing, we are given a set of items and a collection of subsets of the items, called demands. For each demand, we are also given a budget....
-
Fall 2013
In this thesis, we consider min-max vehicle routing problems, specifically min-max tour cover and star cover problems. Given a metric (V,c) and a number k, a set of tours (respectively stars) in G is called a k-tour cover (respectively k-star cover), if they cover all the vertices of G. In the...
-
Approximation Algorithms for Throughput Maximization, Resource Minimization for Fire Containment and Hierarchical Clustering
DownloadFall 2021
In this thesis, we present a variety of approximation algorithms for Resource Minimization for Fire Containment, Throughput Maximization, and Hierarchical Clustering.Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph....
-
Fall 2011
In this thesis, we present a variety of approximation algorithms for the Unsplittable Flow on Paths problem and some Traveling Salesman problems. The main contribution to the Unsplittable Flow on Paths problem is a logarithmic approximation algorithm which is the first non-trivial approximation...
-
Improved approximation algorithms for Min-Max Tree Cover, Bounded Tree Cover, Shallow-Light and Buy-at-Bulk k-Steiner Tree, and (k, 2)-Subgraph
DownloadFall 2011
In this thesis we provide improved approximation algorithms for the Min-Max k-Tree Cover, Bounded Tree Cover and Shallow-Light k-Steiner Tree, (k, 2)-subgraph problems. In Chapter 2 we consider the Min-Max k -Tree Cover (MMkTC). Given a graph G = (V, E ) with weights w: E → Z+ , a set T1, T2, ......