Approximation Algorithms for some Min-max Vehicle Routing Problems

  • Author / Creator
    Jorati, Amin
  • 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 rooted variant, the locations of the roots are given in the input. In Chapter 2, we improve on the approximation ratios of tour cover problems. We present algorithms that improve the approximation ratios of rooted and unrooted min-max k-tour cover problems to (7+epsilon) and (16/3+epsilon) respectively. In Chapter 3, we study the unrooted min-max k-star cover problem and improve the bi-criteria approximation ratio to (O(1/epsilon), 1+epsilon). For the line metric, we present a QPTAS, and in the special case that the stars are non-crossing, we present a PTAS. Then, we show that the problem is APX-hard on the Euclidean metric.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Master of Science
  • 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
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Salavatipour, Mohammad (Computing Science)
  • Examining committee members and their departments
    • Hayward, Ryan (Computing Science)
    • Elmallah, Ehab (Computing Science)