Estoy emocionadísimo ahora mismo, y también contento. Finalmente creo que tengo una prueba de que los algoritmos dados en el papel "Adaptive Sorting..." son 2-aproximaciones. Me alegro mucho. ¡Y que suerte que la prueba funciona para los algoritmos ya existentes!
Qué chisme que ahora la prueba me parece tan simple. A lo menos tengo muchas ideas para mejorar el límite del problema—de estos algoritmos o con otros no lo sé, pero la idea de buscar secuencias ascendencias es muy prometedor. Por supuesto, es una magnitud más compleja tratar de establecer un límite más estricto.
Ay, ¡qué alivio!
I'm incredibly excited right now, and contented. I think I finally have a proof that the algorithms in the "Adaptive Sorting..." are already 2-approximations. I'm so happy to have finally dispelled my last nagging doubts. And what good luck that the proof works for the already-existing algorithms!
I can't believe how simple the proof is. But, at least I have some ideas for how to improve the bounds even further—of these greedy algorithms or with others I don't know yet, but the idea of searching for ascending sequences is promising. Of course, that road is an order of magnitude more complex.
Ah, what a relief!