research
∙
08/11/2023
Simpler constant factor approximation algorithms for weighted flow time – now for any p-norm
A prominent problem in scheduling theory is the weighted flow time probl...
share
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...
research
∙
03/04/2023
Optimizing Low Dimensional Functions over the Integers
We consider box-constrained integer programs with objective g(Wx) + c^T ...
research
∙
11/25/2022
Better Trees for Santa Claus
We revisit the problem max-min degree arborescence, which was introduced...
research
∙
11/09/2022
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
The starting point of this paper is the problem of scheduling n jobs wit...
research
∙
08/05/2022
A PTAS for Minimizing Weighted Flow Time on a Single Machine
An important objective in scheduling literature is to minimize the sum o...
research
∙
02/04/2022
Flow Time Scheduling and Prefix Beck-Fiala
We relate discrepancy theory with the classic scheduling problems of min...
research
∙
01/13/2022
Cardinality Constrained Scheduling in Online Models
Makespan minimization on parallel identical machines is a classical and ...
research
∙
10/06/2021
Towards Non-Uniform k-Center with Constant Types of Radii
In the Non-Uniform k-Center problem we need to cover a finite metric spa...
research
∙
07/28/2021
Load Balancing: The Long Road from Theory to Practice
There is a long history of approximation schemes for the problem of sche...
research
∙
05/09/2021
Knapsack and Subset Sum with Small Items
Knapsack and Subset Sum are fundamental NP-hard problems in combinatoria...
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
∙
11/11/2020
A (2+ε)-approximation algorithm for preemptive weighted flow time on a single machine
Weighted flow time is a fundamental and very well-studied objective func...
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/18/2020
Additive Approximation Schemes for Load Balancing Problems
In this paper we introduce the concept of additive approximation schemes...
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
∙
04/27/2020
Robust Algorithms under Adversarial Injections
In this paper, we study streaming and online algorithms in the context o...
research
∙
05/21/2019
Approximation results for makespan minimization with budgeted uncertainty
We study approximation algorithms for the problem of minimizing the make...
research
∙
04/13/2019
Online Bin Covering with Limited Migration
Semi-online models where decisions may be revoked in a limited way have ...
research
∙
11/02/2018
Local search breaks 1.75 for Graph Balancing
Graph Balancing is the problem of orienting the edges of a weighted mult...
research
∙
11/02/2018
Near-Linear Time Algorithm for n-fold ILPs via Color Coding
We study an important case of ILPs {c^Tx Ax = b, l ≤ x ≤ u, x ∈Z^n t...
research
∙
07/10/2018
A note on the integrality gap of the configuration LP for restricted Santa Claus
In the restricted Santa Claus problem we are given resources R and play...
research
∙
03/13/2018