Sharat Ibrahimpur
Sharat Ibrahimpur
I am currently a Research Officer in Algorithms and Optimisation at the London School of Economics, hosted by László Végh and Neil Olver. I received my M.Math and PhD degrees in Combinatorics and Optimization from the University of Waterloo where I was advised by Chaitanya Swamy. My undergraduate degree was in Applied Mathematics at the Indian Institute of Technology Roorkee.

I am mainly interested in designing approximation algorithms for combinatorial optimization problems, with a recent focus on stochastic optimization. I have broadly worked on problems arising in Network Design, Scheduling / Load Balancing, and Caching.

Between May and October 2021, I was a part-time research intern at Google Research, hosted by Manish Purohit.

A recent version of my CV is here. My publications can also be found on ORCiD, DBLP and Google Scholar.


Publications:
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals [APPROX 2023, arXiv]
(with Ishan Bansal, Joseph Cheriyan, and Logan Grout)

Efficient Caching with Reserves via Marking [ICALP 2023, arXiv]
(with Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang)

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions [ICALP 2023, arXiv]
(with Ishan Bansal, Joseph Cheriyan, and Logan Grout)

Approximation Algorithms for Flexible Graph Connectivity [MathProg 2023, FSTTCS 2021, arXiv]
(with Sylvia Boyd, Joseph Cheriyan, and Arash Haddadan)

Caching with Reserves [APPROX 2022, arXiv]
(with Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang)

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case [SIDMA 2022, APPROX 2020, arXiv]
(with Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Zoltán Szigeti, and Lu Wang)

A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing
[SOSA 2022, arXiv]
(with Chaitanya Swamy)

Minimum-Norm Load Balancing is (almost) as Easy as Minimizing Makespan [ICALP 2021]
(with Chaitanya Swamy)

Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization [FOCS 2020, arXiv]
(with Chaitanya Swamy)

Min-Max Theorems for Packing and Covering Odd (u,v)-trails [IPCO 2017, arXiv]
(with Chaitanya Swamy)