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.
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]