  In the Maximum Independent Set of Hyperrectangles problem, we are given a set
of $n$ (possibly overlapping) $d$-dimensional axis-aligned hyperrectangles, and
the goal is to find a subset of non-overlapping hyperrectangles of maximum
cardinality. For $d=1$, this corresponds to the classical Interval Scheduling
problem, where a simple greedy algorithm returns an optimal solution. In the
offline setting, for $d$-dimensional hyperrectangles, polynomial time $(\log
n)^{O(d)}$-approximation algorithms are known. However, the problem becomes
notably challenging in the online setting, where the input objects
(hyperrectangles) appear one by one in an adversarial order, and on the arrival
of an object, the algorithm needs to make an immediate and irrevocable decision
whether or not to select the object while maintaining the feasibility. Even for
interval scheduling, an $\Omega(n)$ lower bound is known on the competitive
ratio.
  To circumvent these negative results, in this work, we study the online
maximum independent set of axis-aligned hyperrectangles in the random-order
arrival model, where the adversary specifies the set of input objects which
then arrive in a uniformly random order. Starting from the prototypical
secretary problem, the random-order model has received significant attention to
study algorithms beyond the worst-case competitive analysis. Surprisingly, we
show that the problem in the random-order model almost matches the best-known
offline approximation guarantees, up to polylogarithmic factors. In particular,
we give a simple $(\log n)^{O(d)}$-competitive algorithm for $d$-dimensional
hyperrectangles in this model, which runs in $\tilde{O_d}(n)$ time. Our
approach also yields $(\log n)^{O(d)}$-competitive algorithms in the
random-order model for more general objects such as $d$-dimensional fat objects
and ellipsoids. Furthermore, our guarantees hold with high probability.
