16 citations · 69 across the 56 of their papers we have counts for
8 papers · 1 filter
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen, William He, Jason Li +1
We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose additio…
Online Algorithms for the Santa Claus Problem
MohammadTaghi Hajiaghayi, MohammadReza Khani, Debmalya Panigrahi +1
The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum va…
Online Paging with Heterogeneous Cache Slots
Marek Chrobak, Samuel Haney, Mehraneh Liaee +4
It is natural to generalize the online -Server problem by allowing each request to specify not only a point , but also a subset of servers that may serve it. For uniform…
A Regression Approach to Learning-Augmented Online Algorithms
Keerti Anand, Rong Ge, Amit Kumar +1
The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since the…
Customizing ML Predictions for Online Algorithms
Keerti Anand, Rong Ge, Debmalya Panigrahi
A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm a…
Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an -time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms…
Online Algorithms with Multiple Predictions
Keerti Anand, Rong Ge, Amit Kumar +1
This paper studies online algorithms augmented with multiple machine-learned predictions. While online algorithms augmented with a single prediction have been extensively studied i…
Near-Linear Time Approximations for Cut Problems via Fair Cuts
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +1
We introduce the notion of {\em fair cuts} as an approach to leverage approximate -mincut (equivalently -maxflow) algorithms in undirected graphs to obtain near-linea…