Vineet Goyal Assistant Professor Industrial Engineering and Operations Research 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 an Assistant 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, revenue management and inventory management problems.

---

CV (pdf)

---

Published and Submitted Papers . (Funding from NSF Grant CMMI 1201116 and Google Research Award is gratefully acknowledged)

• A Markov Chain Approximation to Choice Modeling. Submitted (2013). (joint with J. Blanchet and G. Gallego)
  

• A Tight Characterization of the Performance of Static Solutions in Two-stage Adjustable Robust Linear Optimization. Submitted (2013). (joint with D. Bertsimas and B. Lu)
  

• Improved Approximations for Two-stage Min-cut and Shortest Path Problems under Uncertainty. Submitted (2012). (joint with D. Golovin, V. Polishchuk, R. Ravi and M. Sysikaski)
  

• Near-Optimal Algorithms for the Assortment Planning Problem under Dynamic Substitution and Stochastic Demand . Under second round revision in Operations Research. (joint with R. Levi and D. Segev)
  

• 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. Invited to Special Issue of Mathematical Methods of Operations Research, 2012. (joint with D. Bertsimas)
  

• On Simulating a Class of Bernstein Polynomials. ACM Transactions on Modeling and Computer Simulation (TOMACS) 22(2), pages 12-20, 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 Andy Sun).
  

• 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 Barbara Anthony, Anupam Gupta, and Viswanath 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)
  

• An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions. Math Programming, Ser. A, pages 1-5, 2009. (joint work with L. Genc-Kaya and R. Ravi).
  

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

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

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

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

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

• 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 Mohit Singh)