Vineet Goyal Associate Professor Industrial Engineering and Operations Research Member, Data Science Institute Columbia University 500 West 120th Street New York, NY 10027 Email: vgoyal AT ieor DOT columbia DOT edu Office: 304 Mudd Tel: (212) 854-0345

---

I am Associate Professor in the Industrial Engineering and Operations Research department at Columbia University. I received my PhD in Algorithms, Combinatorics and Optimization (ACO) in 2008 from Tepper School of Business, CMU where my advisor was R. Ravi. Before joining Columbia, I spent a couple of years as a postdoctoral associate at the Operations Research Center, MIT working with Dimitris Bertsimas.

My research interests include dynamic optimization and decision making under uncertainty. I am interested in the design of tractable approaches for dynamic optimization problems under uncertainty and their applications in electricity markets and revenue management problems.

---

Grants and Awards. Funding support of the following grants and awards is gratefully acknowledged.

• Amazon Faculty Research Award (2019)
• DARPA Lagrange Grant (March 2018-August 2019, with PI: Dan Bienstock and co-PIs: Garud Iyengar and Jose Blanchet)
• NSF Grant CMMI 1636046 (2016-2019, $323K): "A Robust Framework for Modeling Preferences and its Applications in Revenue Management"
• Adobe Digital Marketing Research Award 2016 (joint with Omar Besbes and Garud Iyengar)
• NSF CAREER Award CMMI 1351838 (2014-2019, $400K): "A Data-driven Robust Approach for Large Scale Dynamic Optimization"
• IBM Faculty Award (2014)
• Google Faculty Research Award (2013)
• NSF Grant CMMI 1201116 (2012-2015, $260K): "New Methodologies for Dynamic Optimization"

---

CV (pdf)

---

PhD Students and Postdocs

• Soufiane Fafe
• Ayoub Foussoul
• Chia-Hao Chang (co-advised with Carri Chan)
• Orestis Papadigenopoulos (Postdoctoral Fellow, co-advised with Assaf Zeevi)
• Harsh Sheth (PhD: 2023, co-advised with Adam Elmachtoub, First Position: Quantitative Researcher, SIG)
• Noemie Perivier (PhD: 2023, co-advised with Eric Balkanski)
• Julien Grand-Clement (PhD: 2021, co-advised with Carri Chan, First Position: HEC Paris)
• Raghav Singal (PhD: 2020, co-advised with Garud Iyengar and Omar Besbes, First Position: Dartmouth (Tuck))
• Kumar Goutam (PhD: 2020, co-advised with Henry Lam, First Position: Amazon)
• Omar El Housni (PhD: 2020, First Position: Cornell Tech)
• Rajan Udwani (Postdoctoral Fellow, co-advised with Garud Iyengar, First Position: Berkeley IEOR)
• Shuangyu Wang (PhD: 2018, co-advised with Garud Iyengar)
• Vashist Avadhanula (PhD: 2018, co-advised with Assaf Zeevi and Shipra Agrawal, First position: Facebook Research)
• Antoine Desir (PhD: 2017, First position: INSEAD Paris)
• Brian Lu (PhD: 2016, First position: Engineers Gate)

---

Journal Papers (Published and Under Review)

• Online Allocation of Reusable Resources: Achieving Optimal Competitive Ratio. Under Review.
  (joint with G. Iyengar and Rajan Udwani)
  

• Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path Based Formulation. Under Review.
  (joint with Rajan Udwani)
  

• A First-Order Approach To Accelerated Value Iteration. Under Review.
  (joint with Julien Grand-Clement)
  

• Robust Policies For Proactive ICU Transfers . Under Review.
  (joint with Carri W. Chan, Julien Grand-Clement and Gabriel J. Escobar)
  

• Robust Assortment Optimization under the Markov Chain Choice Model. Under Review(2021).
  (joint with Antoine Desir, J. Zhang).
  

• A Generalized Markov Chain Model to Capture Dynamic Preferences and Choice Overload. Under Review.
  (joint with Goutam Kumar and Agathe Soret). First Prize in INFORMS OR Undergraduate Student Paper Competition, 2018.
  

• Robust Markov Decision Process: Beyond Rectangularity. Under Review.
  (joint with Julien Grand-Clement)
  

• Thompson Sampling for the MNL-Bandit. Under Review.
  (joint with S. Agrawal, Vashist Avadhanula and A. Zeevi). A preliminary version appeared in COLT 2017.
  

• Shapley Meets Uniform: An Axiomatic Framework for Attribution in Online Advertising. Under Review
  (joint with Raghav Singal, O. Besbes, Antoine Desir, Garud Iyengar). Second place in the 2019 Revenue Management and Pricing student paper competition.
  

• On the Optimality of Affine Policies for Budgeted Uncertainty Sets. To Appear in Mathematics of Operations Research.
  (joint with Omar El Housni). Second place in 2020 INFORMS George Nicholson Student Paper Competition.
  

• Capacity Constrained Assortment Optimization under the Markov chain based Choice Model. Management Science, 66(2), pages 698-721, 2020.
  (joint with Antoine Desir, D. Segev and Chun Ye). Selected as finalist in INFORMS George Nicholson Student Paper Competition.
  

• MNL-Bandit: A Dynamic Learning Approach to Assortment Selection. Operations Research, 67(5), pages 1453-1485, 2019.
  (joint with S. Agrawal, Vashist Avadhanula and A. Zeevi)
  

• A Tractable Approach for Designing Piecewise Affine Policies in Dynamic Robust Optimization. Math Programming (forthcoming)
  (joint with A. Ben-Tal and Omar El Housni).
  

• On the Adaptivity Gap in Two-stage Robust Linear Optimization under Uncertain Constraints. Math Programming, 173, pages 313-352, 2019.
  (joint with P. Awasthi and Brian Lu). Selected as finalist in INFORMS George Nicholson Student Paper Competition (2015).
  

• Piecewise Static Policies for Two-stage Adjustable Robust Linear Optimization. Math Programming 169, pages 649-665, 2018.
  (joint with Omar El Housni). Selected as finalist in INFORMS Undergraduate OR Student Paper Competition (2015).
  

• A Markov Chain Approximation to Choice Modeling. Operations Research 64(4), pages 886-905, 2016. MSOM Society Best paper Award (2019) in Operations Research.
  (joint with J. Blanchet and G. Gallego)

• Sparse Process Flexibility Designs: Is Long Chain Really Optimal? Operations Research 64(2), pages 416-431, 2016.
  (joint with Antoine Desir, Y. Wei and J. Zhang). Selected as finalist in INFORMS George Nicholson Student Paper Competition (2014) and MSOM Student Paper Competition (2014).

• Near-Optimal Algorithms for the Assortment Planning Problem under Dynamic Substitution and Stochastic Demand . Operations Research 64(1), pages 219-235, 2016.
  (joint with R. Levi and D. Segev)

• On the Tightness of an LP Relaxation for Rational Optimization and its Applications. Operations Research Letters 44(5), pages 612-617, 2016.
  (joint with Vashist Avadhanula , Jalaj Bhandari and A. Zeevi)
  

• Improved Approximations for Two-stage Min-cut and Shortest Path Problems under Uncertainty. Math Programming 149 (1-2), pages 167-194, 2015.
  (joint with D. Golovin, V. Polishchuk, R. Ravi and M. Sysikaski)
  

• A Tight Characterization of the Performance of Static Solutions in Two-stage Adjustable Robust Linear Optimization. Math Programming 150(2), pages 281-319, 2014.
  (joint with D. Bertsimas and Brian Lu). Updated proofs of reformulations of the static robust problem for general convex sets can be found in this note
  

• An FPTAS for Minimizing a Class of Quasi-Concave Functions over a Convex Set. Operations Research Letters 41(2), pages 191-196, 2013.
  (joint with R. Ravi)
  

• On the Approximability of Adjustable Robust Convex Optimization under Uncertainty. Mathematical Methods of Operations Research, 77(3), pages 323-343, 2013.
  (joint with D. Bertsimas)
  

• On Simulating a Class of Bernstein Polynomials. ACM Transactions on Modeling and Computer Simulation (TOMACS) 22(2), Article 12, 2012.
  (joint with K. Sigman)
  

• On the Power and Limitations of Affine Policies in Two-Stage Adaptive Optimization Problems. Math Programming 134(2), pages 491-531, 2012.
  (joint with D. Bertsimas)
  

• A Geometric Characterization of the Power of Finite Adaptability in Multi-stage Stochastic and Adaptive Optimization. Math of Operations Research 36(1), pages 24-54, 2011.
  (joint with D. Bertsimas and A. Sun).
  

• An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions. Math Programming, 126(2), pages 401-405, 2011.
  (joint work with L. Genc-Kaya and R. Ravi).
  

• On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems. Math of Operations Research, 35(2), pages 284-305, 2010.
  (joint work with D. Bertsimas)
  

• A Plant Location Guide for the Unsure . Math of Operations Research, 35(1), pages 79-101, 2010.
  (joint work with B. Anthony, A. Gupta, and V. Nagarjan).
  

• A PTAS for Chance-Constrained Knapsack Problem with Random Item Sizes. Operations Research Letters, 38(3), pages 161-164, 2010.
  (joint with R. Ravi)
  

• MIP Reformulations for Probabilistic Set Covering Problem. Math Programming, 121(1), pages 1-31, 2008.
  (joint work with M. Lejeune and A. Saxena)
  

---

Papers in Refereed Conferences

• Beyond Worst-case: A Probabilistic Analysis of Affine Policies in Dynamic Optimization. To Appear in Advances in Neural Information Processing Systems (NIPS), 2017.
  (joint with Omar El Housni)
  

• Thompson Sampling for the MNL-Bandit. In COLT (2017).
  (joint with S. Agrawal, Vashist Avadhanula and A. Zeevi)
  

• Assortment Optimization under the Mallows Model. Advances in Neural Information Processing Systems (NIPS), 2016.
  (joint with Antoine Desir, S. Jagabathula and D. Segev)
  

• Assortment Optimization under a Random Swap based Distribution over Permutations Model. In ACM Conference on Electronic Commerce (EC), 2016.
  (joint with Antoine Desir and D. Segev)
  

• A Near-Optimal Exploration-Exploitation Approach for Assortment Selection. In ACM Conference on Electronic Commerce (EC), 2016.
  (joint with S. Agrawal, Vashist Avadhanula and A. Zeevi)
  

• Optimal Price Rebates for Demand Response under Power Flow Constraints. In IEEE SmartGridComm, 2014.
  (joint with G. Iyengar and Q. Schwarz and Shuangyu Wang)
  

• Near-Optimal Execution Policies for Demand-Response Contracts in Electricity Markets. In IEEE Conference on Decision and Control (CDC), 2013.
  (joint with G. Iyengar and Zhen Qiu)
  

• A Markov Chain Approximation to Choice Modeling. In ACM Conference for Electronic Commerce (EC), 2013.
  (joint with J. Blanchet and G. Gallego)
  

• A Plant Location Guide for the Unsure . In SODA 2008.
  (joint work with B. Anthony, A. Gupta, and V. Nagarjan).
  

• Pricing Tree Access Networks with Connected Backbones. In ESA 2007.
  (joint with Anupam Gupta, Stefano Leonardi and R. Ravi)
  

• Pay Today for a Rainy Day: Improved Approximations for Demand-Robust Min-Cut and Shortest Path Problems. In STACS 2006.
  (joint with D. Golovin and R. Ravi)
  

• How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. In FOCS 2005.
  (joint with K. Dhamdhere,   R. Ravi  and  M. Singh)

• On the Crossing Spanning Tree Problem. In APPROX-RANDOM 2004. Latest Version of the paper is here.
  (Joint with V. Bilo,  R. Ravi  and  M. Singh.)

---

Technical Reports

• Balanced Facility Location. GSIA Tech Report 2004.
  (Joint work with R. Ravi)

• A 5/4-approximation for the 2-edge connected subgraph problem on hamiltonian graphs. Tech Report, June 2003. IIT Delhi.
  (Joint work with Naveen Garg,  Akash M Kushal  and M. Singh)