2 citations · 2 across the 8 of their papers we have counts for
14 papers
Stochastic Load Balancing with Machine Reservations
David Alemán Espinosa, Naveen Garg, Sharat Ibrahimpur +2
We introduce a novel variant of stochastic load balancing that enables a quantitative tradeoff between the practical benefits of non-adaptive policies and their performance limitat…
Approximation Algorithms for Norm-Budgeted Packing Problems
David Aleman Espinosa, Sharat Ibrahimpur, Chaitanya Swamy
In recent years, much attention has been devoted to the study of optimization problems under norm-based objectives coming from the rich class of monotone, symmetric norms (and thei…
An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
Sharat Ibrahimpur, László A. Végh
In the Flexible Graph Connectivity (FGC) problem, we are given an undirected multigraph on vertices with nonnegative edge costs, where each edge is classified as either safe or…
Efficient Caching with Reserves via Marking
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis -- including potential functions…
Extensions of the -Flexible-Graph-Connectivity model
Ishan Bansal, Joseph Cheriyan, Logan Grout +1
We present approximation algorithms for network design problems in some models related to the -FGC model. Adjiashvili, Hommelsheim and Mühlenthaler introduced the model of F…
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
Ishan Bansal, Joseph Cheriyan, Logan Grout +1
We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via t…
Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
Ishan Bansal, Joe Cheriyan, Logan Grout +1
The -Steiner-2NCS problem is as follows: Given a constant , and an undirected connected graph , non-negative costs on , and a partition of in…
Caching with Reserves
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Caching is a crucial component of many computer systems, so naturally it is a well-studied topic in algorithm design. Much of traditional caching research studies cache management…
Approximation Algorithms for Flexible Graph Connectivity
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan +1
We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Conn…
A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing
Sharat Ibrahimpur, Chaitanya Swamy
We consider the Vector Scheduling problem on identical machines: we have m machines, and a set J of n jobs, where each job j has a processing-time vector $p_j\in \mathbb{R}^d_{\geq…
A -Approximation Algorithm for Flexible Graph Connectivity
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan +1
We present a -approximation algorithm for the Flexible Graph Connectivity problem [AHM20] via a reduction to the minimum cost -out -arborescence problem.
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization
Sharat Ibrahimpur, Chaitanya Swamy
Motivated by the need for, and growing interest in, modeling uncertainty in data, we introduce and study {\em stochastic minimum-norm optimization}. We have an underlying combinato…
A -Approximation Algorithm for the Minimum -Edge Connected Multisubgraph Problem in the Half-Integral Case
S. Boyd, J. Cheriyan, R. Cummings +4
Given a connected undirected graph on vertices, and non-negative edge costs , the 2ECM problem is that of finding a -edge~connected spanning multisubgraph of $\…
Min-Max Theorems for Packing and Covering Odd -trails
Sharat Ibrahimpur, Chaitanya Swamy
We investigate the problem of packing and covering odd -trails in a graph. A -trail is a -walk that is allowed to have repeated vertices but no repeated edges.…