Combinatorial Optimization Reading Group - Paul LawrenceExport this event to calendar

Friday, September 23, 2022 — 12:00 PM EDT

Title: On the Adaptivity Gap of Stochastic Orienteering

Speaker: Paul Lawrence
Affiliation: University of Waterloo
Location: MC 6029, please contact Rian Neogi for Zoom link

Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution. The objective is to compute a path originating at x that maximizes expected reward among processed jobs, subject to the total distance traveled plus processing times not exceeding our budget. We will discuss the proof of a lower bound on the adaptivity gap of this problem, first on directed graphs and then on undirected graphs. Given time, we will mention additional results by the authors on the correlated stochastic orienteering problem

Event tags 

S M T W T F S
25
26
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
2
3
4
5
  1. 2022 (115)
    1. October (6)
    2. September (11)
    3. August (2)
    4. July (17)
    5. June (17)
    6. May (10)
    7. April (12)
    8. March (18)
    9. February (10)
    10. January (13)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)