Mengapa dugaan serakah begitu sulit?

Baru-baru ini saya belajar tentang dugaan serakah untuk Masalah Superstring Terpendek .

Dalam masalah ini, kita diberi satu set string $s_1,\dots, s_n$ dan kami ingin menemukan terpendek superstring $s$ yaitu sehingga setiap $s_i$ muncul sebagai substring dari $s$ .

Masalah ini NP-hard dan setelah kertas yang panjang, algoritma pendekatan yang paling dikenal untuk masalah ini memiliki rasio $2+\frac{11}{30}$ [Paluch '14].

Dalam praktiknya, ahli biologi menggunakan algoritma Greedy berikut:

Pada setiap langkah, gabungkan dua string yang memiliki tumpang tindih maksimum pada semua pasangan (akhiran maksimum yang merupakan awalan dari string lain), dan ulangi pada instance baru ini hingga hanya ada satu string yang tersisa (yang merupakan superstring dari semua string input) )

Batas bawah $2$ dalam rasio pendekatan Algoritma Greedy ini dapat diperoleh dari input $c(ab)^k,(ba)^k,(ab)^kc$ .

$2$ perkiraan untuk Masalah Superstring Terpendek. Saya sangat terkejut melihat bahwa algoritma yang alami dan mudah seperti itu sangat sulit untuk dianalisis.

Adakah intuisi, fakta, pengamatan, contoh yang menunjukkan mengapa pertanyaan ini begitu menantang?

Pertama-tama saya coba meringkas apa yang diketahui tentang dugaan serakah.

1. Blum, Jiang, Li, Tromp, Yannakakis membuktikan bahwa Gregor Algorithm memberikan 4-aproksimasi, dan Kaplan dan Shafrir menunjukkan bahwa ia memberikan 3,5-aproksimasi untuk masalah Shortest Common Superstring.
2. Versi algoritma serakah diketahui memberikan 3-perkiraan ( Blum, Jiang, Li, Tromp, Yannakakis ).
3. $3$$4$ ).
4. Dugaan Greedy berlaku jika Algoritma Greedy terjadi untuk menggabungkan string dalam beberapa urutan tertentu ( Weinard, Schnitger ; Laube, Weinard ).
5. Algoritma Greedy memberikan 2-aproksimasi kompresi Tarhio, Ukkonen (yang didefinisikan sebagai total panjang string input dikurangi panjang superstring umum terpendek).
6. Ada implementasi yang sangat efisien dari Ukkonen Algoritma Greedy .

Saya pikir salah satu alasan mengapa sulit untuk membuktikan dugaan serakah mungkin sebagai berikut. Sebagian besar pendekatan untuk membuktikan jaminan aproksimasi dari Greedy Algorithm menganalisis grafik tumpang tindih (atau, ekuivalen, grafik awalan) dari set input string. Kita hanya tahu beberapa properti dari grafik ini (seperti ketidaksetaraan Monge dan Triple), tetapi properti ini terbukti tidak cukup untuk membuktikan dugaan serakah ( Weinard, Schnitger ; Laube, Weinard ).