research
∙
07/17/2023
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
In this paper we study the relation of two fundamental problems in sched...
share
research
∙
11/25/2022
Better Trees for Santa Claus
We revisit the problem max-min degree arborescence, which was introduced...
research
∙
02/15/2022
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
The Matching Augmentation Problem (MAP) has recently received significan...
research
∙
11/19/2021
An Improved Analysis of Greedy for Online Steiner Forest
This paper considers the classic Online Steiner Forest problem where one...
research
∙
11/13/2020
The Submodular Santa Claus Problem in the Restricted Assignment Case
The submodular Santa Claus problem was introduced in a seminal work by G...
research
∙
10/22/2020
The Primal-Dual method for Learning Augmented Algorithms
The extension of classical online algorithms when provided with predicti...
research
∙
10/22/2020
Learning Augmented Energy Minimization via Speed Scaling
As power management has become a primary concern in modern data centers,...
research
∙
07/17/2020
The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
We consider hypergraphs on vertices P∪ R where each hyperedge contains e...
research
∙
02/13/2019
Local approximation of the Maximum Cut in regular graphs
This paper is devoted to the distributed complexity of finding an approx...
research
∙
09/21/2018