非表示:
キーワード:
Computer Science, Data Structures and Algorithms, cs.DS
要旨:
The \emph{Temp Secretary Problem} was recently introduced by Fiat et al. It
is a generalization of the Secretary Problem, in which commitments are
temporary for a fixed duration. We present a simple online algorithm with
improved performance guarantees for cases already considered by Fiat et al.\
and give competitive ratios for new generalizations of the problem. In the
classical setting, where candidates have identical contract durations $\gamma
\ll 1$ and we are allowed to hire up to $B$ candidates simultaneously, our
algorithm is $(\frac{1}{2} - O(\sqrt{\gamma}))$-competitive. For large $B$, the
bound improves to $1 - O\left(\frac{1}{\sqrt{B}}\right) - O(\sqrt{\gamma})$.
Furthermore we generalize the problem from cardinality constraints towards
general packing constraints. We achieve a competitive ratio of $1 -
O\left(\sqrt{\frac{(1+\log d + \log B)}{B}}\right) -O(\sqrt{\gamma})$, where
$d$ is the sparsity of the constraint matrix and $B$ is generalized to the
capacity ratio of linear constraints. Additionally we extend the problem
towards arbitrary hiring durations.
Our algorithmic approach is a relaxation that aggregates all temporal
constraints into a non-temporal constraint. Then we apply a linear scaling
algorithm that, on every arrival, computes a tentative solution on the input
that is known up to this point. This tentative solution uses the non-temporal,
relaxed constraints scaled down linearly by the amount of time that has already
passed.
