Marco Molinaro

I am a 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.

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

Current teaching

• 2024.2 - Analise de Algoritmos
  
• 2024.2 - Projeto e Analise de Algoritmos (pos)
  

Previous teaching (PUC)

• 2024.1 - Analise de Algoritmos
  
• 2024.1 - Projeto e Analise de Algoritmos (pos)
  
• 2023.2 - Analise de Algoritmos
  
• 2023.2 - Projeto e Analise de Algoritmos (pos)
  
• 2023.1 - Analise de Algoritmos
  
• 2023.1 - Projeto e Analise de Algoritmos (pos)
  
• 2022.2 - Analise de Algoritmos
  
• 2022.2 - Algoritmos e Incerteza (pos)
  
• 2021.2 - Estruturas Discretas
  
• 2021.2 - Projeto e Analise de Algoritmos (pos)
  
• 2021.1 - Estruturas Discretas
  
• 2021.1 - Analise de Algoritmos
  
• 2020.2 - Algoritmos e Incerteza (pos)
  
• 2020.2 - Estruturas Discretas
  
• 2020.1 - Projeto e Analise de Algoritmos (pos)
  
• 2020.1 - Estruturas Discretas
  
• 2019.2 - Projeto e Analise de Algoritmos (pos)
  
• 2019.2 - Estruturas Discretas
  
• 2019.1 - Analise de Algoritmos
  
• 2019.1 - Algoritmos e Incerteza (pos)
  
• 2018.2 - Analise de Algoritmos
  
• 2018.2 - Algoritmos e Incerteza (pos)
  
• 2018.1 - Analise de Algoritmos
  
• 2018.1 - Projeto e Analise de Algoritmos (pos)
  
• 2017.2 - Estruturas Discretas
  
• 2017.2 - Projeto e Analise de Algoritmos (pos)
  
• 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

• Non-monotonicity of Branching Rules with Respect to Linear Relaxations
  Submitted to Informs Journal on Computing
  With Santanu Dey and Prachi Shah
  
  
• Decision Trees with Short Explainable Rules
  Submitted to Theoretical Computer Science
  With Ferdinando Cicalese, Victor Feitosa, and Eduardo Laber
  
  
• Information Complexity of Mixed-integer Convex Optimization
  Accepted to Math Programming
  With Amitabh Basu, Hongyi Jiang, and Phillip Kerger
  
  
• The Power of Migrations in Dynamic Bin Packing
  Accepted to Sigmetrics 2025
  With Konstantina Mellou and Rudy Zhou
  
  
• A Theoretical and Computational Analysis of Full Strong-Branching
  Math Programming, 2024
  With Santanu Dey, Yatharth Dubey, and Prachi Shah
  
  
• A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
  ICML 2024
  With Amitabh Basu, Hongyi Jiang, and Phillip Kerger
  
  
• Supermodular Approximation of Norms and Applications
  STOC 2024
  With Thomas Kesselheim and Sahil Singla
  
  
• Time-Constrained Learning
  Pattern Recognition, 2023
  With Sergio Filho, Eduardo Laber, and Pedro Lazera
  
  
• Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing
  Discrete and Computational Geometry, 2023
  With C.J. Argue and Anupam Gupta
  
  
• Lower Bounds on the Size of General Branch-and-Bound Trees
  Math Programming, 2023
  With Santanu Dey and Yatharth Dubey
  
  
• Online Demand Scheduling with Failovers
  ICALP 2023
  With Konstantina Mellou and Rudy Zhou
  
  
• Online and Bandit Algorithms Beyond lp norms
  SODA, 2023
  With Thomas Kesselheim and Sahil Singla
  
  
• Virtual Machine Allocation with Lifetime Predictions
  MLSys 2023
  With Hugo Barbalho, Patricia Kovaleski, Beibin Li, Luke Marshall, Abhisek Pan, Eli Cortez, Matheus Leao, Harsh Patwari, Zuzu Tang, Tamires Santos, Larissa Gonçalves, David Dion, Thomas Moscibroda, and Ishai Menache
  
  
• Information Complexity of Mixed-integer Convex Optimization
  IPCO 2023
  With Amitabh Basu, Hongyi Jiang, and Phillip Kerger
  
  
• Curvature of Feasible Sets in Offline and Online Optimization
  Math of Operations Research, 2022
  
  
• Decision Trees with Short Explainable Rules
  NeurIPS, 2022
  With Ferdinando Cicalese, Victor Feitosa, and Eduardo Laber
  
  
• Solving sparse principal component analysis with global support
  Math Programming, 2022
  With Santanu Dey and Guanyi Wang
  
  
• Sparse PSD approximation of the PSD cone
  Math Programming, 191, 2022
  With Grigoriy Blekherman, Santanu Dey, and Shengding Sun
  
  
• Robust Secretary and Prophet Algorithms for Packing Integer Programs
  SODA 2022
  With CJ Argue, Anupam Gupta, and Sahil Singla
  
  
• Branch-and-Bound Solves Random Binary IPs in Polytime
  SODA 2021
  With Santanu Dey and Yatharth Dubey
  
  
• Robust Algorithms for Online Convex Problems via Primal-Dual
  SODA 2021
  
  
• Teaching with Limited Information on the Learner's Behaviour
  ICML 2020
  With Ferdinando Cicalese, Sergio Freitas, and Eduardo Laber
  
  
• Knapsack Secretary with Bursty Adversary
  ICALP 2020
  With Thomas Kesselheim
  
  
• Lower bounds on the lattice-free rank for packing and covering integer programs
  SIAM Journal on Optimization, 29 (1), 2019
  With Merve Bodur, Alberto del Pia, and Santanu Dey
  
  
• k-Servers with a Smile: Online Algorithms via Projections / presentation
  SODA 2019
  With Niv Buchbinder, Anupam Gupta, and Seffi Naor
  
  
• Stochastic lp Load Balancing and Moment Problems via the L-Function Method / presentation
  SODA 2019.
  
  
• Binary Partitions with Approximate Minimum Impurity
  ICML 2018.
  With Eduardo Laber and Felipe Pereira.
  
  
• Maximizing Profit with Convex Costs in the Random-order Model / presentation
  ICALP 2018.
  With Anupam Gupta and Ruta Mehta
  
  
• Minimal Cut-generating Functions are Nearly Extreme
  Math Programming, 172 (1-2), 2018. Preliminary version in IPCO 2016.
  With Amitabh Basu and Robert Hildebrand.
  
  
• Theoretical challenges towards cutting-plane selection
  Math Programming, 170 (1), 2018.
  With Santanu Dey.
  
  
• Aggregation-based cutting-planes for packing and covering integer programs
  Math Programming, 171 (1-2), 2018.
  With Merve Bodur, Alberto del Pia, Santanu Dey, and Sebastian Pokutta.
  
  
• Improving the Randomization Step in Feasibility Pump / instances and results
  SIAM Journal on Optimization, 28 (1), 2018.
  With Santanu Dey, Andres Iroume, and Domenico Salvagnin.
  
  
• Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs
  Math of Operations Research, 43 (1), 2018.
  With Santanu Dey and Qianyi Wang.
  
  
• Online and Random-order Load Balancing Simultaneously / presentation
  SODA 2017.
  
  
• 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.
  
  
• How the Experts Algorithm Can Solve LPs Online / presentation
  Math of Operations Research, 41(4), 2016. Preliminary version in ESA 2014.
  With Anupam Gupta.
  
  
• 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.
  
  
• Testing Lipschitz Functions on Hypergrid Domain
  Algorithmica, 74, 2016. Preliminary version in RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha, and Sofya Raskhodnikova.
  
  
• 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, 7, 2015. Preliminary version in RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha, and Sofya Raskhodnikova.
  
  
• 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
  Operations 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.
  
  
• 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.
  
  
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching / presentation
  SODA 2013.
  With David Woodruff and Grigory Yaroslavtsev.
  
  
• 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.
  
  
• 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.
  
  
• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
  FOCS 2011.
  With Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi.
  
  
• A Probabilistic Analysis of the Strength of the Split and Triangle Closures / presentation
  IPCO 2011.
  With Amitabh Basu and Gerard Cornuejols.
  
  
• 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.
  
  
• Improved Approximations for the Hotlink Assignment Problem
  ACM Transactions on Algorithms, 7(3), 2011.
  With 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.
  
  

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