This is an archive of papers published while I was a PhD candidate in the Theory Group in the Computer Science Department at Stanford advised by Ashish Goel and later a postdoctoral fellow in the Department of Combinatorics & Optimization at the University of Waterloo. My research interests are in algorithm design and theoretical computer science, particularly combinatorial optimization and linear programming.
See also my DBLP and arXiv pages.
This page may be out of date.
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.
SIAM Journal on Computing, 47(4): 1667-1704 (2018)
42nd International Colloquium on Automata, Languages, and Programming (ICALP),
2015.
[arXiv]
[Journal]
Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems
Ian Post, Chaitanya Swamy.
26th ACM-SIAM Symposium on Discrete Algorithms (SODA),
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.
Mathematics of Operations Research, 40(4): 859-868 (2015)
24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
Second place in the George Nicholson Student Paper Competition, 2013.
[arXiv]
[Journal]
[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 (SODA), 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 (EC),
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 (FOCS),
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 (FOCS),
2009.
[arXiv]
[Proceedings]