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- 9Approximation algorithms
- 1Algorithmics
- 1Amortized analysis
- 1Bioinformatics
- 1Capacitated Multicast Routing
- 1Capacitated multicast routing
-
2008
Cai, Zhipeng, Lin, Guohui, Want, Lusheng, Chen, Zhi-Zhong
Technical report TR08-06. The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal...
-
2011
Goebel, Randy, Wang, Lusheng, Lin, Guohui, Li, Zhong
Technical report TR11-02. Given two genomic maps G1 and G2 each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G1 and G2 such that the resultant subsequences, denoted as G1* and G2*, can be partitioned into...
-
Fall 2012
In this thesis, we present some approximation algorithms for the following clustering problems: Minimum Sum of Radii (MSR), Minimum Sum of Diameters (MSD), and Unsplittable Capacitated Facility Location. Given a metric (V, d) and an integer k, we consider the problem of partitioning the points...
-
Fall 2023
In this thesis, we design approximation algorithms for a variety of problems in Network Design. The first problem we consider is the Directed Steiner Tree (DST) problem where we want to find a cheapest way of connecting a subset of nodes (terminal nodes) from a root node in a directed network. We...
-
Spring 2019
Many real-world problems can be formulated as combinatorial optimization problems, thus making it very important to find efficient methods to solve them, both theoretically and practically. In this thesis, we consider several NP-hard combinatorial optimization problems, consisting of some...
-
Fall 2015
How to evaluate the performance of an algorithm is a very important subject in computer science, for understanding its applicability, for understanding the problem which it is applied to, and for the development of new ideas that help to improve the existing algorithms. There are two main...
-
2004
Cai, Zhipeng, Lin, Guohui, Xue, Guoliang
Technical report TR04-12. For the Capacitated Multicast Routing Problem, we considered two models which are the Multicast k-Path Routing and the Multicast k-Tree Routing. We presented two improved approximation algorithms for them, which have worst case performance ratios of 3 and (2 + ρ) (ρ is...
-
2003
Chen, Zhi-Zhong, Xu, Ying, Wen, Jianjun, Lin, Guohui, Jiang, Tao, Xu, Dong, Rizzi, Romeo
Technical report TR03-07. Protein NMR peak assignment refers to the process of assigning a group of \"spin systems\" obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination....
-
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...