Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Multistage Online Maxmin Allocation of Indivisible Entities   We consider an online allocation problem that involves a set $P$ of $n$
players and a set $E$ of $m$ indivisible entities over discrete time steps
$1,2,\ldots,\tau$. At each time step $t \in [1,\tau]$, for every entity $e \in
E$, there is a restriction list $L_t(e)$ that prescribes the subset of players
to whom $e$ can be assigned and a non-negative value $v_t(e,p)$ of $e$ to every
player $p \in P$. The sets $P$ and $E$ are fixed beforehand. The sets
$L_t(\cdot)$ and values $v_t(\cdot,\cdot)$ are given in an online fashion. An
allocation is a distribution of $E$ among $P$, and we are interested in the
minimum total value of the entities received by a player according to the
allocation. In the static case, it is NP-hard to find an optimal allocation the
maximizes this minimum value. On the other hand, $\rho$-approximation
algorithms have been developed for certain values of $\rho \in (0,1]$. We
propose a $w$-lookahead algorithm for the multistage online maxmin allocation
problem for any fixed $w \geq 1$ in which the restriction lists and values of
entities may change between time steps, and there is a fixed stability reward
for an entity to be assigned to the same player from one time step to the next.
The objective is to maximize the sum of the minimum values and stability
rewards over the time steps $1, 2, \ldots, \tau$. Our algorithm achieves a
competitive ratio of $(1-c)\rho$, where $c$ is the positive root of the
equation $wc^2 = \rho (w+1)(1-c)$. When $w = 1$, it is greater than
$\frac{\rho}{4\rho+2} + \frac{\rho}{10}$, which improves upon the previous
ratio of $\frac{\rho}{4\rho+2 - 2^{1-\tau}(2\rho+1)}$ obtained for the case of
1-lookahead.

5
The categories of this paper are: gr-qc
23
The categories of this paper are: solv-int
26
The categories of this paper are: bayes-an
15
The categories of this paper are: nucl-ex
16
The categories of this paper are: stat
25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg
9
The categories of this paper are: nlin
13
The categories of this paper are: quant-ph
3
The categories of this paper are: physics
7
The categories of this paper are: hep-th
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
32
The categories of this paper are: atom-ph
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio