  Recently, the first online complexity class, AOC, was introduced. The class
consists of many online problems where each request must be either accepted or
rejected, and the aim is to either minimize or maximize the number of accepted
requests, while maintaining a feasible solution. All AOC-complete problems
(including Independent Set, Vertex Cover, Dominating Set, and Set Cover) have
essentially the same advice complexity. In this paper, we study weighted
versions of problems in AOC, i.e., each request comes with a weight and the aim
is to either minimize or maximize the total weight of the accepted requests. In
contrast to the unweighted versions, we show that there is a significant
difference in the advice complexity of complete minimization and maximization
problems. We also show that our algorithmic techniques for dealing with
weighted requests can be extended to work for non-complete AOC problems such as
maximum matching (giving better results than what follow from the general AOC
results) and even non-AOC problems such as scheduling.
