Failure diagnosis with incomplete information in cable networks
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1+α for split-delivery VRPSD, and 2+α for unsplit-delivery VRPSD; here α is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4) 149-158; Altinkemer, K., B. Gavish. 1990. Heuristics for delivery problems with constant error guarantees. Transportation Res. 24(4) 294-297]. We also show that the "cyclic heuristic" for split-delivery VRPSD achieves a constant approximation ratio, as conjectured in Bertsimas [Bertsimas, D. J. 1992. A vehicle routing problem with stochastic demand. Oper. Res. 40(3) 574-585]. © 2012 INFORMS.
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
David A. Selby
IBM J. Res. Dev
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev