Approximating Partition in Deterministic Near-Linear Time

We propose a deterministic $\widetilde{O}(n + \frac{1}ε)$-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a polylogarithmic factor) assuming SETH (Strong Exponential Time Hypothesis) [Abboud, Bringmann, Hermelin, and Shabt...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής

Κύριοι συγγραφείς:	Chen, Lin, Lian, Jiayi, Mao, Yuchen, Zhang, Guochuan
Μορφή:	Άρθρο
Έκδοση:	2025
Θέματα:	Data Structures and Algorithms
Διαθέσιμο Online:	https://arxiv.org/abs/2501.12848 http://arxiv.org/abs/2501.12848
Ετικέτες:	Προσθήκη ετικέτας Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!