Approximation Algorithms under the Worst-case Analysis and the Smoothed Analysis

• Author / Creator

  Tong, Weitian

• 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 factors, i.e. the performance measure and the analysis model, that affect the evaluation of an algorithm. In this thesis, we analyse algorithms with approximation ratio as a measure under the worst-case analysis and the smoothed analysis. In particular, several interesting discrete optimization problems from bioinformatics, networking and graph theory are investigated, and currently the best approximation algorithms are designed for them under the classic analysis model — the worst-case analysis and the more ``realistic" model — the smoothed analysis.

• Subjects / Keywords

  • Approximation algorithms
  • Worst-case analysis
  • Smoothed analysis

• Graduation date

  Fall 2015

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3SN01G26

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.