Concept

Competitive ratio

The worst share of the best possible result that a rule acting without knowledge of the future is guaranteed to achieve. It compares an online rule with an offline one that sees the whole input in advance, taking the worst input for the rule.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Half of what an oracle takes

Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.

probability · Optimal stopping

The same rule in the adversary's order and in a random order. Two copies of the 8-a-side triangular graph matched greedily with the worst ranking: 4 matched in the adversary's order, 5 in a random order (average 5.30).

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

discrete · Halls theorem

Named alongside it

The objects these essays reach for when they reach for this one.

Bipartite graph Bound Conditional probability Decision procedure Expectation Greedy algorithm Irrevocable decision Matching Online algorithm Optimal stopping Random permutation Randomisation

All concepts