Marco Molinaro

I am a fifth year Ph.D. student in the Algorithms, Combinatorics and Optimization (ACO) program at Carnegie Mellon University. I am very fortunate to be advised by Prof. Gerard Cornuejols.

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.

Starting Fall 2013, I will be joining Georgia Tech's ISyE department as an Assistant Professor.

CV: [pdf]
Email: lastname[AT]cmu[DOT]edu

Publications (please send me an email for papers which are not available for donwload)

Optimization Under Uncertainty

• Kidney Exchanges and the Query-commit Problem
  Submitted.
  Joint work with R. Ravi.
  
  
• The Geometry of Online Packing Linear Programs
  Math of Operations Research, to appear. Preliminary version in ICALP 2012.
  Joint work with R. Ravi.
  
  
• Improved Approximation Algorithms for the Average-Case Tree Searching Problem
  Algorithmica, to appear. Preliminary version in ICALP 2010 (merged with "On the Complexity of Searching..." below).
  Joint work with Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  
• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
  FOCS 2011.
  Joint work 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.
  Joint work 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.
  Joint work with Eduardo Laber.
  
  
• On Greedy Algorithms for Decision Trees
  ISAAC 2010.
  Joint work with Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  

Sublinear Algorithms

• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
  SODA 2013.
  Joint work with David Woodruff and Grigory Yaroslavtsev.
  
  
• Testing Lipschitz Functions on Hypergrid Domain
  RANDOM 2012.
  Joint work with Pranjal Awasthi, Madhav Jha and Sofya Raskhodnikova.
  
  
• Limitations of Local Filters of Lipschitz and Monotone Functions
  RANDOM 2012.
  Joint work with Pranjal Awasthi, Madhav Jha and Sofya Raskhodnikova.
  
  

Integer Programming and Discrete Optimization

• Characterization of the Split Closure by Cut Generating functions via Geometric Lifting
  In preparation.
  Joint work with Amitabh Basu.
  
  
• Cutting Planes from Two-Term Disjunctions
  Submitted.
  Joint work with Pierre Bonami, Michelle Conforti, Gerard Cornuejols and Giacomo Zambelli.
  
  
• On the Relative Strength of Different Generalizations of Split Cuts
  Submitted.
  Joint work with Sanjeeb Dash and Oktay Gunluk.
  
  
• Lifting Gomory Cuts with Bounded Variables
  Operations Research Letters, 41, 2013.
  Joint work with Gerard Cornuejols and Tamas Kis.
  
  
• A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
  SIAM Journal on Optimization, to appear.
  Joint work with Amitabh Basu, Robert Hildebrand and Matthias Koeppe.
  
  
• A 3-Slope Theorem for the 2-d Infinite Relaxation [presentation]
  Math Programming, to appear.
  Joint work with Gerard Cornuejols.
  
  
• A Probabilistic Analysis of the Strength of the Split and Triangle Closures [presentation]
  IPCO 2011.
  Joint work with Amitabh Basu and Gerard Cornuejols.
  
  
• Capacitated Vehicle Routing with Non-Uniform Speeds [presentation]
  IPCO 2011.
  Joint work with Inge Li Gortz, Viswanath Nagarajan and R. Ravi.
  
  
• Improved Approximations for the Hotlink Assignment Problem
  ACM Transactions on Algorithms, 7(3), 2011.
  Joint work with Eduardo Laber.
  
  

Additional Research

• Cognitive Resource Concentration and Versatility: A New Lens for Understanding Team Diversity
  In preparation.
  Joint work with Ishani Aggarwal and Anita Woolley
  
  
• A Multi-Agent Architecture for a Dynamic Supply Chain Management
  FLAIRS 2006.
  Joint work 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.
  Joint work 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.
  Joint work 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.