In 1988, Finnish computer scientists Esko Ukkonen and Jorma Tarhio conjectured that the simple greedy algorithm for shortest common superstring has a worst-case approximation ratio of 2. Amazingly, the problem is still open almost 40 years later, despite substantial efforts and partial results by many authors (see e.g. https://arxiv.org/abs/2407.20422v1 for a survey of what is […]