University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Chaitanya SwamyExport this event to calendar

Friday, October 3, 2014 — 3:30 PM EDT

Approximation Algorithms for Vehicle-Routing Problems

Speaker: Chaitanya Swamy
Affiliation: University of Waterloo
Room: Mathematics 3 (M3) 3103

Abstract: 

Vehicle-routing problems (VRPs) constitute a broad class of combinatorial-optimization problems that have been widely studied in both the operations research and computer science literature. Despite this, there remain significant gaps in our understanding of these problems, especially from the perspective of designing efficient algorithms with worst-case approximation guarantees. A fundamental difficulty here stems from our lack of understanding of linear-programming (LP) relaxations for VRPs.

I will describe how to leverage LP-based techniques to successfully tackle two classes of VRPs and obtain strong approximation guarantees for these problems. These are: (a) the classical minimum-latency problem and its multi-vehicle and multi-depot extensions, wherein we seek routes for one or more vehicles that together visit all nodes and minimize the sum of the node-waiting times; and (b) regret-bounded VRPs, wherein regret of a node measures its waiting time relative to its shortest-path distance from the depot, and we seek routes that ensure bounded node regret. Our techniques show how to exploit so-called configuration LPs and bidirected LP-relaxations, which are two classes of LPs that are often believed to be quite powerful (in theory and practice), but have only sporadically been leveraged for vehicle-routing and network-design problems.
The talk will be self-contained.

Location 
M3 - Mathematics 3
3103
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2021 (74)
    1. August (5)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)