Renato Werneck

Photo taken by Mihai Budiu in 2012.I am a Computer Scientist whose research interests include algorithms, algorithm engineering, combinatorial optimization, and data structures.

Based in California, I’m currently a Senior Principal Scientist at Amazon‘s Modeling and Optimization (MOP) team. Until September 2014, I was a Senior Researcher at Microsoft Research Silicon Valley, where I had the privilege of working with some wonderful colleagues.

My CV is available here (PDF). I can be reached at rwerneck@cs.princeton.edu.

 

Publications

Also check my Google Scholar profile and DBLP.

Journal Publications

  1. Customizable Point-of-Interest Queries in Road Networks, with D. Delling. IEEE Transactions on Knowledge and Data Engineering, vol. 27, no. 3, pp. 686-698, IEEE, 2015. [pdf]
  2. Customizable Route Planning in Road Networks, with D. Delling, A. V. Goldberg, and T. Pajor. Transportation Science, INFORMS, 2015. [pdf]
  3. Round-Based Public Transit Routing, with D. Delling and T. Pajor. Transportation Science, INFORMS, 2014 (to appear). [pdf]
  4. An Exact Combinatorial Algorithm for Minimum Graph Bisection, with D. Delling, D. Fleischman, A. V. Goldberg, and I. Razenshteyn. Mathematical Programming Series A, Springer, 2014. [pdf]
  5. Alternative Routes in Road Networks, with I. Abraham, D. Delling, and A. V. Goldberg. ACM Journal of Experimental Algorithmics, vol. 18, no. 1, pp. 1-17, ACM, 2013. [pdf]
  6. PHAST: Hardware-Accelerated Shortest Path Trees, with D. Delling, A. V. Goldberg, and A. Nowatzyk. Journal of Parallel and Distributed Computing, Elsevier, 2013. [pdf]
  7. Fast Local Search for the Steiner Problem in Graphs, with E. Uchoa. ACM Journal of Experimental Algorithmics, vol. 17, no. 1, pp. 2.2, ACM, 2012. [pdf]
  8. Fast Local Search for the Maximum Independent Set Problem, with D. V. Andrade and M. G. C. Resende. Journal of Heuristics, vol. 18, no. 4, pp. 525-547, Springer, 2012. [pdf]
  9. Data Structures for Mergeable Trees, with L. Georgiadis, H. Kaplan, N. Shafrir, and R. E. Tarjan. ACM Transaction on Algorithms, vol. 7, no. 2, pp. 14:1-14:30, ACM, 2011.
  10. Shortest Paths in Road Networks: From Practice to Theory and Back, with D. Delling and A.V. Goldberg. Information Technology, vol. 53, no. 6, pp. 294-301, 2011.
  11. Dynamic Trees in Practice, with R. E. Tarjan. ACM Journal of Experimental Algorithmics, vol. 14, no. 4, pp. 4.5:1-4.5:21, ACM, 2009. [pdf]
  12. Shortest-Path Feasibility Algorithms: An Experimental Evaluation, with B. V. Cherkassky, L. Georgiadis, A. V. Goldberg, and R. E. Tarjan. ACM Journal of Experimental Algorithmics, vol. 14, no. 2, pp. 2.7:1-2.7:37, ACM, 2009.
  13. A fast swap-based local search procedure for location problems, with M. G. C. Resende. Annals of Operations Research, volume 150, number 1, pp. 205-230, 2007. [pdf]
  14. Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem, with R. Fukasawa, H. Longo, J. Lysgaard, M. Poggi de Aragao, M. Reis, and E. Uchoa. Mathematical Programming, volume 106, number 3, pp. 491-511, 2006. [pdf]
  15. Finding Dominators in Practice, with L. Georgiadis and R. E. Tarjan. Journal of Graph Algorithms and Applications, volume 10, no.1, pp. 69-94, 2006. [pdf]
  16. A hybrid multistart heuristic for the uncapacitated facility location problem, with M. G. C. Resende. European Journal of Operations Research, volume 174, number 1, pp. 54-68, 2006. [pdf]
  17. A hybrid heuristic for the p-median problem, with M. G. C. Resende. Journal of Heuristics, volume 10, number 1, pp. 59-88, 2004. [pdf]
  18. New benchmark instances for the Steiner problem in graphs, with I. Rosseti, M. Poggi de Aragao, C. C. Ribeiro, and E. Uchoa. In Metaheuristics: Computer Decision-Making (M. G. C. Resende and J. Souza, editors), pp. 601-614, Kluwer, 2003. [pdf]
  19. A hybrid GRASP with perturbations for the Steiner problem in graphs, with C. C. Ribeiro and E. Uchoa. INFORMS Journal on Computing, volume 14, number 3, pp. 228-246, 2002. [pdf]
  20. Finding minimum congestion spanning trees, with J. C. Setubal. ACM Journal of Experimental Algorithmics, volume 5, 2000. [pdf]

Book Chapters

  1. Hub Labeling (2-Hop Labeling), with D. Delling and A. V. Goldberg. In Encyclopedia of Algorithms, Ming-Yang Kao (editor), 2015. [pdf]
  2. Reach for A*: Shortest Path Algorithms with Preprocessing, with A. V. Goldberg and H. Kaplan. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pp. 93-140, AMS, 2009. [pdf]
  3. Dynamic Trees. In Encyclopedia of Algorithms, Ming-Yang Kao (editor), 2008. [pdf]

Conference Proceedings

  1. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search, with Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, and Robert E. Tarjan. In European Symposium on Algorithms (ESA), LNCS, Springer-Verlag, 2015 (to appear). [pdf]
  2. Public Transit Labeling, with D. Delling, J. Dibbelt, and T. Pajor. In International Symposium on Experimental Algorithms (SEA), pp. 273-285, Springer, 2015. [report]
  3. Sketch-based Influence Computation: Scaling up with Guarantees, with E. Cohen, D. Delling, and T. Pajor. In ACM International Conference on Information and Knowledge Management (CIKM), ACM, 2014. [report]
  4. Computing Classic Closeness Centrality, at Scale, with E. Cohen, D. Delling, and T. Pajor. In ACM Conference on Online Social Networks (COSN), ACM, 2014. (Best paper award.) [report]
  5. Robust Distance Queries on Massive Networks, with D. Delling, A. V. Goldberg, and T. Pajor. In European Symposium on Algorithms (ESA), Springer, 2014. [report]
  6. Customizing Driving Directions with GPUs, with D. Delling and M. Kobitzsch. In International Conference on Parallel Processing (Euro-Par), Springer, 2014. [pdf]
  7. Hub Labels: Theory and Practice, with D. Delling, A. V. Goldberg, and R. Savchenko. In International Symposium on Experimental Algorithms (SEA), Springer, 2014. [pdf]
  8. Customizable Point-of-Interest Queries in Road Networks, with D. Delling. In SIGSPATIAL GIS, pp. 490-493, ACM, 2013. [pdf]
  9. Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths, with E. Cohen, D. Delling, F. Fuchs, A. V. Goldberg, and M. Goldszmidt. In ACM Conference on Online Social Networks (COSN), ACM, 2013. [pdf]
  10. Hub Label Compression, with D. Delling and A. V. Goldberg. In International Symposium on Experimental Algorithms (SEA), Springer, 2013. [pdf]
  11. Faster Customization of Road Networks, with D. Delling. In International Symposium on Experimental Algorithms (SEA), Springer, 2013. [pdf]
  12. Computing Multimodal Journeys in Practice, with D. Delling, J. Dibbelt, T. Pajor, and D. Wagner. In International Symposium on Experimental Algorithms (SEA), Springer, 2013. [pdf]
  13. HLDB: Location-Based Services in Databases, with I. Abraham, D. Delling, A. Fiat, and A. V. Goldberg. In SIGSPATIAL GIS, ACM, 2012. (Best paper award.) [pdf]
  14. Hierarchical Hub Labelings for Shortest Paths, with I. Abraham, D. Delling, and A. V. Goldberg. In European Symposium on Algorithms (ESA), Springer, 2012. [pdf]
  15. Better Bounds for Graph Bisection, with D. Delling. In European Symposium on Algorithms (ESA), Springer, 2012. [pdf]
  16. Exact Combinatorial Branch-and-Bound for Graph Bisection, with D. Delling, A. V. Goldberg, and I. Razenshteyn. In Meeting on Algorithm Engineering and Experiments (ALENEX), SIAM, 2012. [pdf]
  17. Round-Based Public Transit Routing, with D. Delling and T. Pajor. In Meeting on Algorithm Engineering and Experiments (ALENEX), SIAM, 2012. [pdf]
  18. Robust Mobile Route Planning with Limited Connectivity, with D. Delling, M. Kobitzsch, and D. Luxen. In Meeting on Algorithm Engineering and Experiments (ALENEX), SIAM, 2012. [pdf]
  19. Maximum Flows by Incremental Breadth-First Search, with A. V. Goldberg, S. Hed, H. Kaplan, and R. E. Tarjan. In European Symposium on Algorithms (ESA), Springer, 2011. [pdf]
  20. VC-Dimension and Shortest Path Algorithms, with I. Abraham, D. Delling, A. Fiat, and A. V. Goldberg. In International Colloquium on Automata Languages and Programming (ICALP), Springer, 2011. [pdf]
  21. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks, with I. Abraham, D. Delling, and A. V. Goldberg. In International Symposium on Experimental Algorithms (SEA), Springer, 2011. [pdf]
  22. Customizable Route Planning, with D. Delling, A. V. Goldberg, and T. Pajor. In International Symposium on Experimental Algorithms (SEA), Springer, 2011. [pdf]
  23. Faster Batched Shortest Paths in Road Networks, with D. Delling and A. V. Goldberg. In Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), OpenAccess Series in Informatics, 2011.
  24. Graph Partitioning with Natural Cuts, with D. Delling, A. V. Goldberg and I. Razenshteyn. In International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2011. [pdf]
  25. PHAST: Hardware-Accelerated Shortest Path Trees, with D. Delling, A. V. Goldberg, A. Nowatzyk. In International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2011. (Best paper award.) [pdf]
  26. DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines, with M. Budiu and D. Delling. In International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2011. [pdf]
  27. Alternative Routes in Road Networks, with I. Abraham, D. Delling, and A. V. Goldberg. In International Symposium on Experimental Algorithms (SEA), Springer, 2010. [pdf]
  28. Fast Local Search for Steiner Trees in Graphs, with E. Uchoa. In Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2010.
  29. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms, with I. Abraham, A. Fiat, and A. V. Goldberg. In ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2010 [pdf]
  30. Virtual Ring Routing Trends, with D. Malkhi, S. Sen, K. Talwar, and U. Wieder. In International Simposium on Distributed Computing (DISC), Springer, 2009. [pdf]
  31. An Experimental Study of Minimum Mean Cycle Algorithms, with with L. Georgiadis, A. V. Goldberg, and R. E. Tarjan. In Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2009.
  32. Fast Local Search for the Maximum Independent Set Problem, with D. V. Andrade and M. G. C. Resende. In Workshop on Efficient Algorithms (WEA), 220-234, Springer, 2008.
  33. Shortest Path Feasibility Algorithms: An Experimental Evaluation, with B. V. Cherkassky, Loukas Georgiadis, A. V. Goldberg, and R. E. Tarjan. In Workshop on Algorithm Engineering and Experiments (ALENEX), San Francisco, California, 2008. [pdf]
  34. Better Landmarks Within Reach, with A. V. Goldberg and Haim Kaplan. In Workshop on Experimental Algorithms (WEA), pp. 38-51, Rome, Italy, 2007. [pdf]
  35. Dynamic Trees in Practice, with R. E. Tarjan. In Workshop on Experimental Algorithms (WEA), pp. 80-93, Rome, Italy, 2007. [pdf]
  36. Reach for A*: Efficient Point-to-Point Shortest Path Algorithms, with A. V. Goldberg and Haim Kaplan. In Workshop on Algorithm Engineering and Experiments (ALENEX), Miami, Florida, 2006. [pdf]
  37. Design of Data Structures for Mergeable Trees, with L. Georgiadis R. E. Tarjan. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 813-882, Miami, Florida, 2006. [pdf]
  38. Computing Point-to-Point Shortest Paths from External Memory, with A. V. Goldberg. In Workshop on Algorithm Engineering and Experiments (ALENEX), Vancouver, Canada, 2005. [pdf]
  39. Self-Adjusting Top Trees, with R. E. Tarjan. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 813-882, Vancouver, Canada, 2005. [pdf]
  40. Finding Dominators in Practice, with L. Georgiadis, R. E. Tarjan, S. Triantafyllis, and D. August. In European Symposium on Algorithms (ESA), Bergen, Norway, LNCS, volume 3221, pp. 677-688, Springer-Verlag, 2004. [pdf]
  41. Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem, with R. Fukasawa, J. Lysgaard, M. Poggi de Aragao, M. Reis, and E. Uchoa. In Integer Programming and Combinatorial Optimization (IPCO), New York, LNCS, volume 3064, pp. 1-15, Springer-Verlag, 2004. [pdf]
  42. On the implementation of a swap-based local search procedure for the p-median problem, with M. G. C. Resende. In Workshop on Algorithm Engineering and Experiments (ALENEX), Richard E. Ladner (Ed.), SIAM, Philadelphia, pp. 119-127, 2003. [pdf]
  43. On the implementation of MST-based heuristics for the Steiner problem in graphs, with M. Poggi de Aragao. In Workshop on Algorithm Engineering and Experiments (ALENEX), San Francisco, LNCS, volume 2409, pp. 1-15, Springer-Verlag, 2002. [pdf]
  44. New benchmark instances for the Steiner problem in graphs, with I. Rosseti, M. Poggi de Aragao, C. C. Ribeiro, and E. Uchoa. In Metaheuristics International Conference (MIC), pp. 557-561, Porto, Portugal, 2001. [pdf]
  45. Hybrid local search for the Steiner problem in graphs, with M. Poggi de Aragao, C. C. Ribeiro, and E. Uchoa. In Metaheuristics International Conference (MIC), pp. 429-433, Porto, Portugal, 2001. [pdf]
  46. Dual heuristics on the exact solution of large Steiner problems, with M. Poggi de Aragao and E. Uchoa. In Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), Fortaleza, Brazil, Electronic Notes in Discrete Mathematics, volume 7, Elsevier, 2001. [pdf]
  47. A hybrid GRASP with perturbations and adaptive path-relinking for the Steiner problem in graphs, with C. C. Ribeiro and E. Uchoa. In Workshop on Algorithm Engineering as a New Paradigm, pp. 76-116, Kyoto University, Japan, 2000. [pdf]
  48. Finding minimum congestion spanning trees, with J. C. Setubal and A. F. Conceicao. In Workshop on Algorithm Engineering (WAE), King’s College, London, LNCS, volume 1668, pp. 60-71, Springer-Verlag, 1999. [pdf]

Other Publications

  1. Route Planning in Transportation Networks, with H. Bast, D. Delling, A. Goldberg, M. Muller-Hannemann, T. Pajor, P. Sanders, and D. Wagner. Technical Report arXiv:1504.05140 (updated from Technical Report MSR-TR-2014-4), 2015.
  2. A Robust and Scalable Algorithm for the Steiner Problem in Graphs, with T. Pajor and E. Uchoa. Technical Report arXiv:1412.2787 (presented at the 11th DIMACS Implementation Challenge: Steiner Tree Problems), 2014.
  3. Timed Influence: Computation and Maximization, with E. Cohen, D. Delling, and T. Pajor. Technical Report arXiv:1410.6976, 2014.
  4. Design and Analysis of Data Structures for Dynamic Trees. PhD Thesis, Princeton University, 2006. [pdf]
  5. Problema de Steiner em Grafos: Algoritmos Primais, Duais e Exatos. Master’s Thesis, Department of Informatics, PUC-Rio, 2001 (in Portuguese).
    (Title in English: Steiner Problem in Graphs: Primal, Dual, and Exact Algorithms.) [pdf]
  6. A program for building contig scaffolds in double-barreled shotgun genome sequencing, with J. C. Setubal. Technical Report IC-01-05, Institute of Computing, Unicamp, 2001. [pdf]
  7. Sorting methods for small arrays, with C. C. Ribeiro. PUC-Rio Department of Informatics Technical Report MCC 23-00, 2000. [pdf]

Last updated on April 16, 2019.