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.
Email: molinaro[dot]marco[AT]gmail[DOT]com
Current teaching
Previous teaching (PUC)
Publications
- Time-Constrained Learning
With Sergio Filho, Eduardo Laber, and Pedro Lazera
- Online Advertiser-Centric Budget Allocation
With Eduardo Cesar Coutinho
- A Theoretical and Computational Analysis of Full Strong-Branching
Accepted to Math Programming
With Santanu Dey, Yatharth Dubey, and Prachi Shah
- Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing
Accepted to Discrete and Computational Geometry
With C.J. Argue and Anupam Gupta
- Lower Bounds on the Size of General Branch-and-Bound Trees
Accepted to Math Programming
With Santanu Dey and Yatharth Dubey
- Solving sparse principal component analysis with global support
Aceepted to Math Programming
With Santanu Dey and Guanyi Wang
- Curvature of Feasible Sets in Offline and Online Optimization
Accepted to Math of Operations Research
- 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.