  In the Shortest Common Superstring problem, one needs to find the shortest
superstring for a set of strings. This problem is APX-hard, and many
approximation algorithms were proposed, with the current best approximation
factor of 2.466. Whereas these algorithms are technically involved, for more
than thirty years the Greedy Conjecture remains unsolved, that states that the
Greedy Algorithm ``take two strings with the maximum overlap; merge them;
repeat'' is a 2-approximation.
  This conjecture is still open, and one way to approach it is to consider its
stronger version, which may make the proof easier due to the stronger premise
or provide insights from its refutation. In this paper, we propose two
directions to strengthen the conjecture. First, we introduce the Locally Greedy
Algorithm (LGA), that selects a pair of strings not with the largest overlap
but with the \emph{locally largest} overlap, that is, the largest among all
pairs of strings with the same first or second string. Second, we change the
quality metric: instead of length, we evaluate the solution by the number of
occurrences of an arbitrary symbol.
  Despite the double strengthening, we prove that LGA is a \emph{uniform}
4-approximation, that is, it always constructs a superstring with no more than
four times as many occurrences of an arbitrary symbol as any other superstring.
At the same time, we discover the limitations of the greedy heuristic: we show
that LGA is at least 3-approximation, and the Greedy Algorithm is at least
uniform 2.5-approximation. These result show that if the Greedy Conjecture is
true, it is not because the Greedy Algorithm is locally greedy or is uniformly
2-approximation.
