Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Bamas, Etienne"'
We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Claus problem and its different variants have been subject to extensive r
Externí odkaz:
http://arxiv.org/abs/2407.04824
Autor:
Bamas, Etienne
This paper is devoted to the study of the MaxMinDegree Arborescence (MMDA) problem in layered directed graphs of depth $\ell\le O(\log n/\log \log n)$, which is an important special case of the Santa Claus problem. Obtaining a polylogarithmic approxi
Externí odkaz:
http://arxiv.org/abs/2406.18273
One of the most popular clustering algorithms is the celebrated $D^\alpha$ seeding algorithm (also know as $k$-means++ when $\alpha=2$) by Arthur and Vassilvitskii (2007), who showed that it guarantees in expectation an $O(2^{2\alpha}\cdot \log k)$-a
Externí odkaz:
http://arxiv.org/abs/2310.13474
In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation, also known as the Santa Claus problem. For both of these problems the
Externí odkaz:
http://arxiv.org/abs/2307.08453
Autor:
Bamas, Étienne, Rohwedder, Lars
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former p
Externí odkaz:
http://arxiv.org/abs/2211.14259
The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap $2$-edge connected subgraphs. This has culminated in a $\frac{5}{3}$-approximation algo
Externí odkaz:
http://arxiv.org/abs/2202.07283
This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k\}\}$ that are required to be connected. The goal is to maintain a min
Externí odkaz:
http://arxiv.org/abs/2111.10086
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem $n$ unsplittable resources have to be assigned to $m$ players
Externí odkaz:
http://arxiv.org/abs/2011.06939
The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm
Externí odkaz:
http://arxiv.org/abs/2010.11632
As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a variant of the classic online speed scaling problem, in which machine
Externí odkaz:
http://arxiv.org/abs/2010.11629