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
Previous teaching (PUC)
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.