Roberto Solis-Oba

photo of Dr Solis-Oba.


Office: Middlesex College 417
Tel: 519-661-2111 ext. 86974x12345

Personal Web Page


Roberto Solis-Oba is a Professor at the Department of Computer Science of the University of Western Ontario. Prof. Solis-Oba received his Ph.D. from Purdue University under the supervision of Prof. Greg Frederickson and he held a postdoctoral position at the Max Planck Institute for Informatics under the guidance of Prof. Kurt Mehlhorn. The research of Prof. Solis-Oba centers on the design of efficient approximation algorithms for NP-hard optimization problems and he has conducted extensive research on network, scheduling, and packing optimization problems.

Prof. Solis-Oba is the co-founder of the Workshop on Approximation and Online Algorithms (WAOA) that has taken place annually since 2003. He has served in the Program Committees of numerous conferences specialized on algorithm design. Prof. Solis-Oba received the Faculty Scholar Award and the USC Teaching Award from the University of Western Ontario.

Research Interests

  1. The design of efficient algorithms for combinatorial optimization problems. He has conducted research in areas such as network optimization, path planning, genome assembly, video game optimization, and geometric packing.
  2. Approximation algorithms for NP-hard optimization problems. Most of his research has been done on approximation algorithms, where he has worked on a large number of problems in areas such as scheduling, network optimization, clustering, packing, matroid optimization, partitioning and labelling problems, and hypergraphs.
  3. The design of efficient algorithms for online problems and problems involving large data sets. His research in this area has included mining for information in very large networks, predictive caching, genome assembly, and search engines.

Selected Publications

  1. Daniel Page* and Roberto Solis-Oba. (2019). Approximation algorithms for the graph balancing problem with two speeds and two job lengths. Journal of Combinatorial Optimization. 37(3): 1045-1070.
  2. Roberto Solis-Oba, Paul Bonsma, and Stefanie Lowski. (2017). A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica. 77(2): 374-388.
  3. Zhendong Shao* and Roberto Solis-Oba. (2018). Labeling Mycielski graphs with a condition at distance two. Ars Combinatoria. 140: 337-349.
  4. Nasim Samei* and Roberto Solis-Oba. (2015). Analysis of a local search algorithm for the k-facility location problem. RAIRO Theoretical Informatics and Applications. 49(4): 285-306.
  5. Lucian Ilie, Bahlul Haider*, Mike Molnar*, Roberto Solis-Oba. (2014). SAGE: String overlap assembly of genomes. BMC Bioinformatics. 15: 302-310.
  6. Jansen and R. Solis-Oba. A polynomial time OPT +1 algorithm for the cutting stock problem with a constant number of object lengths. In Mathematics of Operations Research, 36(4), 743–753, 2011.
  7. Jansen, M. Mastrolilli*, and R. Solis-Oba. Job shop scheduling problems with controllable processing times. In European Journal of Operational Research, 167 (2), 2005, 297–319.
  8. Jansen, R. Solis-Oba, and M. Sviridenko. Makespan minimization in job shops: a polynomial time approximation scheme. In SIAM Journal on Discrete Mathematics, 16(2), 2003, pp. 288–300.
  9. Sanders and R. Solis-Oba. How helpers hasten h-relations. In Journal of Algorithms, 41, 2001, pp. 86-98.
  10. Frederickson and R. Solis-Oba. Increasing the weight of minimum spanning trees. In Journal of Algorithms, 33, 1999, pp. 244-266.


Course taught in 2020/2021
  • CS 2210A: Data Structures and Algorithms

  •  CS2210B: Data Structures and Algorithms

  •  CS4438B: Internet Algorithmics

  •  CS9668B: Internet Algorithmics


  • Faculty Scholar

  •  USC Teaching Award

  •  Western Award of Excellence in Undergraduate Teaching