  In this paper, we exploit linear programming duality in the online setting
(i.e., where input arrives on the fly) from the unique perspective of designing
lower bounds on the competitive ratio. In particular, we provide a general
technique for obtaining online deterministic and randomized lower bounds (i.e.,
hardness results) on the competitive ratio for a wide variety of problems. We
show the usefulness of our approach by providing new, tight lower bounds for
three diverse online problems. The three problems we show tight lower bounds
for are the Vector Bin Packing problem, Ad-auctions (and various online
matching problems), and the Capital Investment problem. Our methods are
sufficiently general that they can also be used to reconstruct existing lower
bounds.
  Our techniques are in stark contrast to previous works, which exploit linear
programming duality to obtain positive results, often via the useful
primal-dual scheme. We design a general recipe with the opposite aim of
obtaining negative results via duality. The general idea behind our approach is
to construct a primal linear program based on a collection of input sequences,
where the objective function corresponds to optimizing the competitive ratio.
We then obtain the corresponding dual linear program and provide a feasible
solution, where the objective function yields a lower bound on the competitive
ratio. Online lower bounds are often achieved by adapting the input sequence
according to an online algorithm's behavior and doing an appropriate ad hoc
case analysis. Using our unifying techniques, we simultaneously combine these
cases into one linear program and achieve online lower bounds via a more robust
analysis. We are confident that our framework can be successfully applied to
produce many more lower bounds for a wide array of online problems.
