Zobrazeno 1 - 10
of 169
pro vyhledávání: '"P. Bamas"'
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
Autor:
Gernot Rohrmoser
Publikováno v:
Momentum Quarterly, Vol 9, Iss 4 (2020)
Der vorliegende Artikel beschäftigt sich mit dalitisch-feministischer Prosa. Anhand einer Analyse von Bamas Roman Sangati wird versucht, die in den Geschichten, Dialogen und Reflexionen transportierten und kodierten gesellschaftskritischen und dalit
Externí odkaz:
https://doaj.org/article/b5df77fd3a8a4ef6bd97183cefb5d684
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
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
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