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
  • Graduation date
    Fall 2015
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • 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.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
  • Supervisor / co-supervisor and their department(s)
  • Examining committee members and their departments
    • Goebel, Randy (Computing Science)
    • Gu, Qianping (Computing Science)
    • Greiner, Russell (Computing Science)
    • Salavatipour, Mohammad (Computing Science)
    • Lin, Guohui (Computing Science)
    • Szepesvari, Csaba (Computing Science)