Ian Post

Address:
Combinatorics & Optimization
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1

I am a postdoctoral fellow in the Department of Combinatorics & Optimization at the University of Waterloo.
Prior to this I was PhD student in the Theory Group in the Computer Science Department at Stanford advised by Ashish Goel.

Research interests: My research interests are in algorithms and optimization, particularly combinatorial optimization and linear programming.

Papers

• Faster Strongly Polynomial Algorithms for Generalized Flow
  Joseph Cheriyan, Ian Post.
  Forthcoming.

• Solving Fast-Mixing Markov Decision Processes
  Ian Post.
  Forthcoming.

• A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
  Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post.
  In submission.

• Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems
  Ian Post, Chaitanya Swamy.
  26th ACM-SIAM Symposium on Discrete Algorithms, 2015.
  [arXiv] [Proceedings]

• Proxy Distribution on Trust Networks
  Ashish Goel, Mohammad Mahdian, Ian Post.
  Manuscript.

• The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes
  Ian Post, Yinyu Ye.
  24th ACM-SIAM Symposium on Discrete Algorithms, 2013.
  Second place in the George Nicholson Student Paper Competition, 2013.
  To appear in Mathematics of Operations Research.
  [arXiv] [Proceedings] [Video of talk (Discrete Geometry and Optimization Workshop at Fields Institute)]

• Online Submodular Welfare Maximization: Greedy is Optimal
  Michael Kapralov, Ian Post, Jan Vondrák.
  24th ACM-SIAM Symposium on Discrete Algorithms, 2013.
  [arXiv] [Proceedings] [Video of talk (Flexible Network Design Workshop at Fields Institute)]

• Embedding Paths into Trees: VM Placement to Minimize Congestion
  Deebojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde.
  Lecture Notes in Computer Science, vol. 7501, Algorithms -- ESA 2012, pages 431--442, 2012.
  [arXiv] [Proceedings]

• Single Pass Sparsification in the Streaming Model with Edge Deletions
  Ashish Goel, Michael Kapralov, Ian Post.
  Manuscript, 2012.
  [arXiv]

• Optimal Bandwidth-Aware VM Allocation for Infrastructure-as-a-Service
  Debojyoti Dutta, Michael Kapralov, Ian Post, Rajendra Shinde.
  Manuscript, 2012.
  [arXiv]

• Liquidity in Credit Networks: A Little Trust Goes a Long Way
  Pranav Dandekar, Ashish Goel, Ramesh Govindan, Ian Post.
  12th ACM Conference on Electronic Commerce, 2011.
  Preliminary version in 2010 Workshop on the Economics of Networks, Systems, and Computation.
  [arXiv] [Proceedings]

• One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
  Ashish Goel, Ian Post.
  Theory of Computing, Special Issue in Honor of Rajeev Motwani, 8(15):315-368, 2012.
  51st Symposium on Foundations of Computer Science, 2010.
  [Journal] [arXiv] [Proceedings] [Video of talk (FOCS 2010)]

• An Oblivious O(1)-Approximation for Single-Source Buy-at-Bulk
  Ashish Goel, Ian Post.
  50th Symposium on Foundations of Computer Science, 2009.
  [arXiv] [Proceedings]