Apa algoritma perkiraan yang baik untuk masalah jumlah subset sejauh ini?

Dengan "baik", maksud saya baik algoritma menyediakan ikatan yang relatif ketat atau memiliki waktu berjalan yang relatif cepat. Setiap referensi diterima.

$\epsilon$O ( n + 1 / ϵ $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$$O(n + 1/ \epsilon)$

Lebih lanjut meningkatkan ini, Kellerer et al. (2003) memberikan FPTAS dengan waktu dan ruang. Selain itu, menjawab pertanyaan Anda tentang "waktu berjalan yang relatif cepat", mereka mencatat bahwa (berdasarkan hasil komputasi) bahwa skema tersebut secara efisien menyelesaikan kasus hingga item dengan kesalahan relatif yang dijamin lebih kecil dari .O ( n + 1 / ε ) 5000 1 /$O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$$O(n+1/ \epsilon)$$5000$$1/1000$

Saya tidak yakin apakah ada hasil yang lebih baru. Seperti disebutkan, karena jumlah subset adalah kasus khusus dari masalah ransel, orang mungkin akan menemukan hasil lebih banyak ketika mencari itu.

PEMBARUAN: Anda mungkin juga ingin melihat The Design of Approximation Algorithms, Williamson and Shmoys, 2011 , lihat bab mulai dari halaman 65 tentang masalah Knapsack. Mereka memberikan FPTAS (pada halaman 68) untuk masalah Knapsack yang berjalan dalam waktu . Mungkin algoritma yang dirancang khusus untuk masalah jumlah Subset lebih cepat daripada yang lebih umum untuk Knapsack.$O(n^3/\epsilon)$