Was sind bisher gute Approximationsalgorithmen für das Teilmengen-Summenproblem?

Antworten:

11

ϵO ( n + 1 / ϵ )O(min{n/ϵ,n+1/ϵ2log(1/ϵ)})O(n+1/ϵ)

Weitere Verbesserung auf diesem Kellerer et al. (2003) gibt ein FPTAS mit Zeit und Raum. Bei der Beantwortung Ihrer Frage zur "relativ schnellen Laufzeit" stellten sie außerdem fest, dass das Schema (basierend auf den Berechnungsergebnissen) Instanzen mit bis zu Elementen mit einem garantierten relativen Fehler von weniger als effizient löst .O ( n + 1 / ε ) 5000 1 / 1000O(min{n1/ϵ,n+1/ϵ2log(1/ϵ)})O(n+1/ϵ)50001/1000

Ich bin mir nicht sicher, ob es neuere Ergebnisse gibt. Wie bereits erwähnt, wird man wahrscheinlich noch mehr Ergebnisse finden, wenn man danach sucht, da die Teilmengen-Summe ein Sonderfall des Rucksackproblems ist.

UPDATE: Vielleicht möchten Sie auch einen Blick auf das Design von Approximationsalgorithmen, Williamson und Shmoys, 2011 werfen. Weitere Informationen finden Sie im Kapitel ab Seite 65 zum Knapsack-Problem. Sie geben ein FPTAS (auf Seite 68) für das Knapsack-Problem an, das in wird. Es kann sein, dass die speziell für das Subset-Summenproblem entwickelten Algorithmen schneller sind als die allgemeineren für den Knapsack.O(n3/ϵ)

Juho
quelle
n ist die Anzahl der zu summierenden ganzen Zahlen, richtig?
Juan Bermejo Vega
@ JuanBermejoVega Richtig!
Juho