Analisis smoothed telah diterapkan berkali-kali untuk memahami runtime dari algoritma yang tepat untuk banyak masalah seperti pemrograman linier dan k-means. Ada hasil yang cukup umum di bidang ini, misalnya Heiko Röglin dan Berthold Vöcking, analisis Smoothing pemrograman integer , 2005. Beberapa hasil umum ini tampaknya mengandalkan lemma isolasi untuk menghasilkan sebuah instance dengan solusi optimal unik. Dengan asumsi , makalah ini mengesampingkan keberadaan algoritma waktu polinomial yang diperhalus untuk masalah N P-keras .
Beberapa pekerjaan telah dilakukan pada analisis yang dihaluskan untuk rasio algoritma aproksimasi. Ada Rao Raghavendra, Probabilistic and Smoothed Analysis of Algorithms Approximation , 2008 yang mencoba untuk memberikan batas perkiraan yang ditingkatkan untuk algoritma Christofides dengan analisis smoothed. Tidak ada rasio perkiraan eksplisit yang diberikan.
Apakah ada alasan mengapa kekerasan hasil pendekatan harus membatasi rasio pendekatan algoritma yang berjalan dalam waktu polinomial yang diperhalus? Apakah hasil dalam makalah Heiko Röglin dan Berthold Vöcking juga berlaku untuk algoritma aproksimasi?
sumber