Computer Science Assistant

Location:

Mountain View, CA

Posted:

February 19, 2013

Contact this candidate

Resume:

Renato Werneck's ResumeRenato F. Werneck

Personal

Home page: http://research.microsoft.com/~renatow/

E-mail: renatowatmicrosoft.com

Address: Microsoft Silicon Valley, 1065 La Avenida, Mountain View, CA 94043

Born December 30, 1976, in Rio de Janeiro, Brazil

Brazilian Citizen

Education

Computer Science Ph.D., 09/2001 to 06/2006

Princeton University, Princeton, NJ

Research Advisor: Professor Robert E. Tarjan

GPA: 4.0/4.0

Computer Science M.A., 09/2001 to 05/2003

Princeton University, Princeton, NJ

Research Advisor: Professor Robert E. Tarjan

GPA: 4.0/4.0

Computer Science M.Sc., 08/1999 to 08/2001

Catholic University of Rio de Janeiro (PUC-Rio), Brazil

Advisor: Professor Marcus Poggi de Arag o

GPA: 10.0/10.0

Computer Engineer (B.Sc.), 03/1995 to 07/1999

State University of Campinas (Unicamp), Brazil

Final Project Advisor: Professor Jo o Carlos Setubal

GPA: 0.9705/1.0000 (highest ever)

Experience

Researcher, Microsoft Research Silicon Valley, 07/2006-present

Research Assistant, Princeton University, 09/2003-06/2006 (with Professor Robert E. Tarjan)

Summer Intern, Microsoft Research Silicon Valley, 06/2005 to 09/2005 (with Dr. Andrew V. Goldberg).

Summer Intern, Microsoft Research Silicon Valley, 06/2004 to 09/2004 (with Dr. Andrew V. Goldberg).

Summer Intern, AT&T Laboratories (Florham Park), 06/2003 to 09/2003 (with Dr. Mauricio G. C. Resende).

Teaching Assistant (Computer Graphics), Princeton University, 02/2003 to 05/2003 (under Professor Adam Finkelstein).

Teaching Assistant (Discrete Mathematics), Princeton University, 09/2002 to 01/2003 (under Professor Moses Charikar).

Summer Intern, AT&T Laboratories (Florham Park), 06/2002 to 09/2002 (with Dr. Mauricio G. C. Resende).

Research Assistant, Optimization Laboratory (LoT), PUC-Rio, 01/2000 to 07/2001 (with Professor Marcus Poggi de Arag o).

Teaching Assistant (Discrete Structures), PUC-Rio, 03/2000 to 07/2000 (under Professor Marcus Poggi de Arag o).

Research Assistant, Bioinformatics Laboratory (LBI), Unicamp, 12/1998 to 06/1999 (with Professor Jo o Carlos Setubal).

Summary of Qualifications

Research experience in Algorithms, Data Structures, Algorithm Engineering, Combinatorial Optimization, Metaheuristics, Computational Biology, and Computer Graphics.

Experience with C, C++, Java, Perl, and ML, among other programming languages.

Experience in Compilers, Networks, Computer Architecture, Computational Geometry, Network Flows.

Awards and Honors

Highest GPA (0.9705 on a 0-1 scale) among majors in technology-related areas (including Engineering) since the foundation of Unicamp (in 1966). Award given in 2006.

Scientific and Technological Medal, awarded in February 2000 by the State of S o Paulo (Brazil), for relevant contribution to the project of genetic sequencing of the phytopathogen Xylella fastidiosa.

Ranked first among applicants to the Computer Science M.Sc. program of PUC-Rio (Brazil), August 1999.

Ranked first in the College Entrance Examination of Unicamp in 1995, with the highest grade since its inception (in 1987).

Ranked first, College Entrance Examination of the University of Bras lia (UnB), 1995.

Ranked first, College Entrance Examination of the Technical Scientific Center, PUC-Rio, 1995.

Scholarships and Grants

Princeton University, Ph.D. Scholarship, 2001-2002.

Brazilian Ministry of Education (CAPES), Ph.D. Scholarship, 2001-2005 (declined).

Brazilian National Research Council (CNPq), Ph.D. Scholarship, 2001-2005 (declined).

Brazilian Ministry of Education (CAPES), M.Sc. Scholarship, 1999-2001.

State of S o Paulo, Brazil (FAPESP), Scientific Initiation Scholarship, 1998-1999.

Brazilian National Research Council (CNPq), Technological and Industrial Initiation Scholarship, 1996.

Journal PublicationsA fast swap-based local search procedure for location problems, with M. G. C. Resende. Annals of Operations Research, volume 150, No. 1, pp. 205-230, 2007.

Finding Dominators in Practice, with L. Georgiadis and R. E. Tarjan. Journal of Graph Algorithms and Applications, volume 10, number 1, pp. 69-94, 2006.

Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem, with R. Fukasawa, H. Longo, J. Lysgaard, M. Poggi de Arag o, M. Reis, and E. Uchoa. Mathematical Programming Series A, volume 106, number 3, pp. 491-511, 2006.

A hybrid multistart heuristic for the uncapacitated facility location problem, with M. G. C. Resende. European Journal of Operational Research, volume 174, number 1, pp. 54-68, 2005.

A hybrid heuristic for the p-median problem, with M. G. C. Resende. Journal of Heuristics, volume 10, number 1, pp. 59-88, 2004.

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.

Finding minimum congestion spanning trees, with J. C. Setubal. ACM Journal of Experimental Algorithmics, volume 5, 2000.

Book ChapterNew benchmark instances for the Steiner problem in graphs, with I. Rosseti, M. Poggi de Arag o, C. C. Ribeiro, and E. Uchoa. In Metaheuristics: Computer Decision-Making, M. G. C. Resende and J. Souza (Eds.), Kluwer, pp. 601-614, 2003.

Conference ProceedingsBetter Landmarks Within Reach, with A. V. Goldberg and H. Kaplan. In Proceedings of the 6th Workshop on Efficient Algorithms (WEA), volume 4525 of Lecture Notes in Computer Science, pp. 38-51, Springer-Verlag, 2007.

Dynamic Trees in Practice, with R. E. Tarjan. In Proceedings of the 6th Workshop on Efficient Algorithms (WEA), volume 4525 of Lecture Notes in Computer Science, pp. 80-93, Springer-Verlag, 2007.

Design of data structures for mergeable trees, with L. Georgiadis and R. E. Tarjan. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 394-403, SIAM, 2006.

Reach for A*: Efficient point-to-point shortest path algorithms, with A. V. Goldberg and H. Kaplan. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2006.

Self-adjusting top trees, with R. E. Tarjan. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 813-822, SIAM, 2005.

Computing point-to-point shortest paths from external memory, with Andrew V. Goldberg. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 26-40, SIAM, 2005.

Finding dominators in practice, with L. Georgiadis, R. E. Tarjan, S. Triantafyllis, and D. August. Proceedings of the 12th Annual European Symposium on Algorithms (ESA), volume 3221 of Lecture Notes in Computer Science, pp. 677-688, Springer-Verlag, 2004.

Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem, with R. Fukasawa, J. Lysgaard, M. Poggi de Arag o, M. Reis, and E. Uchoa. In Integer Programming and Combinatorial Optimization - 10th International IPCO Conference, New York, volume 3064 of Lecture Notes in Computer Science, pp. 1-15, Springer-Verlag, 2004.

On the implementation of a swap-based local search procedure for the p-median problem, with M. G. C. Resende. Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, pp. 119-127, SIAM, 2003.

On the implementation of MST-based heuristics for the Steiner problem in graphs, with M. Poggi de Arag o. Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX), San Francisco, pp. 1-15, SIAM, 2002.

New benchmark instances for the Steiner problem in graphs, with I. Rosseti, M. Poggi de Arag o, C. C. Ribeiro, and E. Uchoa. Extended abstract in Extended Abstracts of the 4th Metaheuristics International Conference (MIC), Porto, Portugal, pp. 557-561, 2001.

Hybrid local search for the Steiner problem in graphs, with M. Poggi de Arag o, C. C. Ribeiro, and E. Uchoa. Extended Abstracts of the 4th Metaheuristics International Conference (MIC), Porto, Portugal, pp. 429-433, 2001.

Dual heuristics on the exact solution of large Steiner problems, with M. Poggi de Arag o and E. Uchoa. Extended abstract in Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), Fortaleza, Brazil, 2001, Electronic Notes in Discrete Mathematics, volume 7, Elsevier, 2001. (Abstract of an early version in Proceedings of the 17th International Symposium on Mathematical Programming (ISMP), Atlanta, 2000.)

Finding minimum congestion spanning trees, with J. C. Setubal and Arlindo Concei o. Proceedings of the Third Workshop on Algorithm Engineering (WAE), King's College, London, volume 1668 of Lecture Notes in Computer Science, pp. 60-71, Springer-Verlag, 1999.

Other PublicationsBetter Landmarks Within Reach. Presented at the 9th DIMACS Challenge: Shortest Paths, 2006.

Design and Analysis of Data Structures for Dynamic Trees, Ph.D. Thesis, Princeton University, 2006.

Reach for A*: Efficient point-to-point shortest path algorithms, with A. V. Goldberg and H. Kaplan. Technical Report MSR-TR-2005-132, Microsoft Research, 2005.

Steiner Problem in Graphs: Primal, Dual, and Exact Algorithms (in Portuguese). Master's Thesis, Department of Informatics, PUC-Rio, 2001.

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.

Computation of generalized Voronoi diagrams using graphics hardware: a fast implementation, with D. Andrade, D. Nehab and D. Tuler (in Portuguese). Abstract presented at the Computer Graphics Seminar, Institute of Pure and Applied Mathematics (IMPA), Rio de Janeiro, Brazil, 2000.

Sorting methods for small arrays, with C. C. Ribeiro. Department of Informatics Technical Report MCC 23-00, Catholic University of Rio de Janeiro (PUC-Rio), Brazil, 2000.

Selected PresentationsBetter Landmaks Within Reach

9th DIMACS Challenge: Shortest Paths, Rutgers University, NJ, 2006.

(Joint work with A. V. Goldberg and H. Kaplan.)

Reach for A*: Fast point-to-point shortest paths on road networks

Microsoft Research, Mountain View, CA, 2005.

(Joint work with A. V. Goldberg and H. Kaplan.)

A framework for dynamic trees

2nd Bertinoro Workshop on Algorithms and Data Structures (ADS 2005), Bertinoro, Italy, 2005.

(Joint work with S. Alstrup, J. Holm, R. E. Tarjan and Mikkel Thorup.)

Self-adjusting top trees

16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, 2005.

(Joint work with R. E. Tarjan.)

Computing point-to-point shortest paths from external memory

7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), Vancouver, Canada, 2005.

(Joint work with A. V. Goldberg.)

Shortest paths from external memory

Microsoft Research, Mountain View, CA, 2004.

(Joint work with A. V. Goldberg.)

A direct implementation of top trees

Workshop on Dynamic Algorithms, New Orleans, LA, 2004.

(Joint work with S. Alstrup, J. Holm, R. E. Tarjan, and M. Thorup.)

On the implementation of a swap-based local search procedure for the p-median problem

5th Workshop on Algorithm Engineering and Experiments (ALENEX'03), Baltimore, MD, 2003.

(Joint work with M. G. C. Resende.)

Heuristics for the p-median problem

Internet and Network Systems Research Center, AT&T Labs Research, Florham Park, NJ, 2002.

(Joint work with M. G. C. Resende.)

On the implementation of MST-based heuristics for the Steiner problem in graphs

4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), San Francisco, CA, 2002.

(Joint work with M. Poggi de Arag o.)

Dual heuristics on the exact solution of large Steiner problems

17th International Symposium on Mathematical Programming (ISMP 2000), Atlanta, GA, 2000.

(Joint work with D. Andrade, M. Poggi de Arag o, and E. Uchoa.)

Computation of generalized Voronoi diagrams using graphics hardware: a fast implementation

Computer Graphics Seminar, Institute of Pure and Applied Mathematics (IMPA), Rio de Janeiro, Brazil, 2000.

(Joint work with D. Andrade, D. Nehab and D. Tuler.)

Other Activities

Program Committee Member for LATIN'08 (Latin American Theoretical Informatics Symposium), WEA'06 (Workshop on Experimental Algorithms), and ALENEX'06 (Workshop on Algorithm Engineering and Experiments).

Referee for ACM Symposium on Theory of Computing (STOC), ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Transactions on Algorithms, Computers and Operations Research, Discrete and Applied Mathematics, IEEE Symposium on Foundations of Computer Science (FOCS), Information Processing Letters, International Journal of Computer Mathematics, International Transactions in Operational Research, Journal of Computer Systems and Sciences, Journal of Heuristics, Latin American Theoretical Informatics Symposium (LATIN), Science, and Workshop on Efficient and Experimental Algorithms (WEA).

Member of PUC-Rio's team on the ACM International Collegiate Programming Contest '99-'00 - South American Regional.

Member of Unicamp's team on the ACM International Collegiate Programming Contest '98-'99 - South American Regional.

Member of the supporting group of the Organizing Committee of the II Brazilian National Collegiate Software Contest. Unicamp, 1997.

Member of the supporting group of the Organizing Committee of the ACM International Collegiate Programming Contest '97-'98 - South American Regional. Unicamp, 1997.

References

Professor Robert E. Tarjan

Professor, Department of Computer Science, Princeton University

Phone: +1-609-***-****

E-mail: ***@**.*********.***

Doctor Andrew V. Goldberg

Principal Researcher, Microsoft Research Silicon Valley

Phone: +1-650-***-****

E-mail: "last-name"@microsoft.com

Doctor Mauricio G. C. Resende

Lead Member of Technical Staff, AT&T Labs Research

Phone: +1-973-***-****