2015/01/26 by Shalabh Vidyarthi, Vidyarthi, Shalabh, K.K. Shukla +1
Decision Sciences · Economics, Econometrics and Finance · Engineering · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1501.06515
openalex publication_date 2015/01/26 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28
We consider the P2P orienteering problem on general metrics and present a\n(2+\ε) approximation algorithm. In the stochastic P2P orienteering\nproblem we are given a metric and each node has a fixed reward and random size.\nThe goal is to devise a strategy for visiting the nodes so as to maximize the\nexpected value of the reward without violating the budget constraints. We\npresent an approximation algorithm for the non-adaptive variant of the P2P\nStochastic orienteering. As an implication of the approximation to the\nstochastic P2P orienteering problem, we define a stochastic vehicle routing\nproblem with time-windows and present a constant factor approximation solution.\n