  In this work, we study online graph problems with monotone-sum objectives. We
propose a general two-fold greedy algorithm that references yardstick
algorithms to achieve $t$-competitiveness while incurring at most
$\frac{w_{\text{max}}\cdot(t+1)}{\min\{1, w_\text{min}\}\cdot(t-1)}$ amortized
recourse, where $w_{\text{max}}$ and $w_{\text{min}}$ are the largest value and
the smallest positive value that can be assigned to an element in the sum. We
further show that the general algorithm can be improved for three classical
graph problems by carefully choosing the referenced algorithm and tuning its
detailed behavior. For Independent Set, we refine the analysis of our general
algorithm and show that $t$-competitiveness can be achieved with
$\frac{t}{t-1}$ amortized recourse. For Maximum Cardinality Matching, we limit
our algorithm's greed to show that $t$-competitiveness can be achieved with
$\frac{(2-t^*)}{(t^*-1)(3-t^*)}+\frac{t^*-1}{3-t^*}$ amortized recourse, where
$t^*$ is the largest number such that $t^*= 1 +\frac{1}{j} \leq t$ for some
integer $j$. For Vertex Cover, we show that our algorithm guarantees a
competitive ratio strictly smaller than $2$ for any finite instance in
polynomial time while incurring at most $3.33$ amortized recourse. We beat the
almost unbreakable $2$-approximation in polynomial time by using the optimal
solution as the reference without computing it. We remark that this online
result can be used as an offline approximation result (without violating the
unique games conjecture) to partially improve upon the constructive algorithm
of Monien and Speckenmeyer.
