3 citations · 5 across the 4 of their papers we have counts for
5 papers · 1 filter
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called \emph{links}. The task is to fin…
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
Christos Kalaitzis, Ola Svensson, Jakub Tarnawski
We consider the classic problem of scheduling jobs on unrelated machines so as to minimize the weighted sum of completion times. Recently, for a small constant , B…
An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem
Christos Kalaitzis
We study the Maximum Budgeted Allocation problem, which is the problem of assigning indivisible items to players with budget constraints. In its most general form, an instance of t…
Combinatorial Algorithm for Restricted Max-Min Fair Allocation
Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson
We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of hav…
On the Configuration LP for Maximum Budgeted Allocation
Christos Kalaitzis, Aleksander Mcadry, Alantha Newman +2
We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of indivisible goods to players, each with a separate budget, such that we maximize the…