Marco Molinaro

I am an Assistant Professor in the Computer Science Department at PUC-RIo. I was previously an Assistant Professor at TU Delft's EWI and at Georgia Tech's ISyE and ACO, and before that a PhD student in the ACO program at Carnegie Mellon University.

My research is broadly concerned with decision-making under limited information and large dimensionality. I examine the different aspects of this program from three main perspectives: Optimization Under Uncertainty, Sublinear Algorithms and Integer Programming and Combinatorial Optimization.

Email: molinaro[dot]marco[AT]gmail[DOT]com

Current teaching

• 2017.2 - Estruturas Discretas
  
• 2017.2 - Projeto e Analise de Algoritmos (pos)
  

Previous teaching (PUC)

• 2017.1 - Analise de Algoritmos
  
• 2017.1 - Algoritmos e Incerteza (pos)
  
• 2016.1 - Analise de Algoritmos
  
• 2016.1 - Projeto e Analise de Algoritmos (pos)
  

Publications

Optimization Under Uncertainty

• Online and Random-order Load Balancing Simultaneously / presentation
  SODA 2017.
  
  
• How the Experts Algorithm Can Solve LPs Online / presentation
  Math of Operations Research, 41(4), 2016. Preliminary version in ESA 2014.
  With Anupam Gupta.
  
  
• The Geometry of Online Packing Linear Programs / presentation
  Math of Operations Research, 39, 2014. Preliminary version in ICALP 2012.
  With R. Ravi.
  
  
• Improved Approximation Algorithms for the Average-Case Tree Searching Problem
  Algorithmica, 68, 2014. Preliminary version in ICALP 2010 (merged with "On the Complexity of Searching..." below).
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  
• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
  FOCS 2011.
  With Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi.
  
  
• On the Complexity of Searching in Trees and Partially Ordered Structures
  Theoretical Computer Science, 412, 2011. Preliminary version in ICALP 2010.
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  
• An Approximation Algorithm for Binary Searching in Trees / presentation
  Algorithmica, 59, 2011. Preliminary version in ICALP 2008
  With Eduardo Laber.
  
  
• On Greedy Algorithms for Decision Trees
  ISAAC 2010.
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  

Sublinear Algorithms

• Amplification of One-Way Information Complexity via Codes and Noise Sensitivity / presentation
  ICALP 2015.
  With David Woodruff and Grigory Yaroslavtsev.
  
  
• Limitations of Local Filters of Lipschitz and Monotone Functions / presentation
  Transactions on Computation Theory, to appear. Preliminary version in RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha and Sofya Raskhodnikova.
  
  
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching / presentation
  SODA 2013.
  With David Woodruff and Grigory Yaroslavtsev.
  
  
• Testing Lipschitz Functions on Hypergrid Domain
  RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha and Sofya Raskhodnikova.
  
  

Integer Programming and Discrete Optimization

• Improving the Randomization Step in Feasibility Pump / instances and results
  Submitted.
  With Santanu Dey, Andres Iroume, and Domenico Salvagnin.
  
  
• Aggregation-based cutting-planes for packing and covering integer programs
  Math Programming, to appear.
  With Merve Bodur, Alberto del Pia, Santanu Dey, and Sebastian Pokutta.
  
  
• Minimal Cut-generating Functions are Nearly Extreme
  Math Programming, to appear. Preliminary version in IPCO 2016.
  With Amitabh Basu and Robert Hildebrand.
  
  
• Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs
  Math of Operations Research, to appear.
  With Santanu Dey and Qianyi Wang.
  
  
• Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
  Math Programming, 162 (1), 2017.
  With Natashia Boland, Santanu Dey, Thomas Kalinowski, and Fabian Rigterink.
  
  
• Mixed-integer Quadratic Programming is in NP / presentation
  Math Programming, 162 (1), 2017.
  With Alberto del Pia and Santanu Dey.
  
  
• Capacitated Vehicle Routing with Non-Uniform Speeds / presentation
  Math of Operations Research, 41 (1), 2016. Preliminary version in IPCO 2011.
  With Inge Li Gortz, Viswanath Nagarajan and R. Ravi.
  
  
• Approximating Polyhedra with Sparse Inequalities / presentation
  Math Programming, 154, 2015. Preliminary version in IPCO 2014.
  With Santanu Dey and Qianyi Wang.
  
  
• Some Lower Bounds on Sparse Outer Approximations of Polytopes / presentation
  Optimization Research Letters, 43 (3), 2015.
  With Santanu Dey and Andres Iroume.
  
  
• Characterization of the Split Closure by Cut Generating functions via Geometric Lifting
  European Journal of Operations Research, 243 (3), 2015.
  With Amitabh Basu.
  
  
• On the Relative Strength of Different Generalizations of Split Cuts / presentation
  Discrete Optimization, 16, 2015.
  With Sanjeeb Dash and Oktay Gunluk.
  
  
• Cutting Planes from Two-Term Disjunctions
  Operations Research Letters, 41, 2013.
  With Pierre Bonami, Michelle Conforti, Gerard Cornuejols and Giacomo Zambelli.
  
  
• Lifting Gomory Cuts with Bounded Variables
  Operations Research Letters, 41, 2013.
  With Gerard Cornuejols and Tamas Kis.
  
  
• A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
  SIAM Journal on Optimization, 23, 2013.
  With Amitabh Basu, Robert Hildebrand and Matthias Koeppe.
  
  
• A 3-Slope Theorem for the 2-d Infinite Relaxation / presentation
  Math Programming, 142, 2013.
  With Gerard Cornuejols.
  
  
• A Probabilistic Analysis of the Strength of the Split and Triangle Closures / presentation
  IPCO 2011.
  With Amitabh Basu and Gerard Cornuejols.
  
  
• Improved Approximations for the Hotlink Assignment Problem
  ACM Transactions on Algorithms, 7(3), 2011.
  With Eduardo Laber.
  
  

Additional Research

• Cognitive Resource Concentration and Versatility: A New Lens for Understanding Team Diversity
  In preparation.
  With Ishani Aggarwal and Anita Woolley
  
  
• A Multi-Agent Architecture for a Dynamic Supply Chain Management
  FLAIRS 2006.
  With Jose Sardinha, Patrick Paranhos, Pedro Cunha, Ruy Milidiu and Carlos Lucena.
  
  
• LearnAgentsSCM - A multi-agent system for the TAC Supply Chain Management
  IJCAI 2005 Poster Section.
  With Jose Sardinha, Patrick Paranhos, Pedro Cunha, Helena Milidiu, Ruy Milidiu and Carlos Lucena.
  
  
• LearnAgents 2005 - A multi-agent system for the TAC Classic
  IJCAI 2005 Poster Section.
  With Jose Sardinha, Patrick Paranhos, Pedro Cunha, Helena Milidiu, Ruy Milidiu and Carlos Lucena.
  
  

Copyright notice: The copyrights of the published papers have been transferred to the respective publishers.