Approximation Algorithms for Some Combinatorial Optimization Problems

• Author / Creator

  Xu, Yao

• 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 classification problems and some computational biology problems, all of which can be formulated in terms of graphs; we focus on the design and analysis of approximation algorithms for these problems. The main techniques used to design and analyze approximation algorithms in this thesis include: randomized rounding (based on linear programming relaxation), local search, and amortization.We investigate the following NP-hard problems in this thesis: the maximum happy vertice (MHV) problem, its complement the minimum unhappy vertices (MUHV) problem, the maximum duo-preservation string mapping (Max-Duo) problem, and the k-path-partition (k-PP) problem. The MHV and MUHV problems, which are actually labeling problems, and the k-PP problem can all be considered as classification problems. The Max-Duo problem isa string comparison problem, with applications in bioinformatics and data compression, and the k-PP problem was actually arising from a broadcasting problem in data communication networks. We present approximation algorithms for MHV and MUHV based on randomized linear programming rounding. For Max-Duo and k-PP with k = 3, we propose improved approximation algorithms mainly based on local search, and the performances of these approximation algorithms are all done through amortized analysis.

• Subjects / Keywords

  • Randomized rounding
  • Vertex happiness
  • String mapping
  • Approximation algorithms
  • Amortized analysis
  • Combinatorial optimization
  • Local search
  • k-path partition

• Graduation date

  Spring 2019

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-6w2b-6f51

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.