We extend the standard online worst-case model to accommodate past experience
which is available to the online player in many practical scenarios. We do this
by revealing a random sample of the adversarial input to the online player
ahead of time. The online player competes with the expected optimal value on
the part of the input that arrives online. Our model bridges between existing
online stochastic models (e.g., items are drawn i.i.d. from a distribution) and
the online worst-case model. We also extend in a similar manner (by revealing a
sample) the online random-order model.
We study the classical secretary problem in our new models. In the worst-case
model we present a simple online algorithm with optimal competitive-ratio for
any sample size. In the random-order model, we also give a simple online
algorithm with an almost tight competitive-ratio for small sample sizes.
Interestingly, we prove that for a large enough sample, no algorithm can be
simultaneously optimal both in the worst-cast and random-order models.

本文研究了在线算法在最坏情况和随机顺序模型中的应用，探讨了秘书问题的解决方法和竞争比的优化。

带样本的竞争分析与秘书问题

Competitive Analysis with a Sample and the Secretary Problem

Relational joins are at the core of relational algebra, which in turn is the
core of the standard database query language SQL. As their evaluation is
expensive and very often dominated by the output size, it is an important task
for database query optimisers to compute estimates on the size of joins and to
find good execution plans for sequences of joins. We study these problems from
a theoretical perspective, both in the worst-case model, and in an average-case
model where the database is chosen according to a known probability
distribution. In the former case, our first key observation is that the
worst-case size of a query is characterised by the fractional edge cover number
of its underlying hypergraph, a combinatorial parameter previously known to
provide an upper bound. We complete the picture by proving a matching lower
bound, and by showing that there exist queries for which the join-project plan
suggested by the fractional edge cover approach may be substantially better
than any join plan that does not use intermediate projections. On the other
hand, we show that in the average-case model, every join-project plan can be
turned into a plan containing no projections in such a way that the expected
time to evaluate the plan increases only by a constant factor independent of
the size of the database. Not surprisingly, the key combinatorial parameter in
this context is the maximum density of the underlying hypergraph. We show how
to make effective use of this parameter to eliminate the projections.

本文研究了从理论角度出发，如何通过计算连接大小的估计值以及查找连接序列的良好执行计划来解决数据库查询优化问题。我们发现，在最坏情况下，查询的最坏大小由其底层超图的分数边覆盖数特征化，而在平均情况下，则是通过底层超图的最大密度属性来消除连接中的投影，提高连接性能。