SMF

New Algorithm for Dense Subset-Sum Problem

New Algorithm for Dense Subset-Sum Problem

Mark CHAIMOVICH
     
                
  • Année : 1999
  • Tome : 258
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : Primary: 90C10 Alternate: 05A17, 11B25, 68Q25
  • Pages : 363-373
  • DOI : 10.24033/ast.460

On présente un nouvel algorithme pour le problème des sommes partielles (subset-sum problem) dans le cas dense. Il est basé sur une caractérisation de la famille des sommes partielles obtenue par des méthodes analytiques de la théorie additive des nombres. L'algorithme fonctionne pour un grand nombre de sommants $(m)$ avec des valeurs qui sont majorées. La borne $(\ell )$ dépend modérément de $m$. Le temps requis par ce nouvel algorithme est en $O(m^{7/4}/\log ^{3/4} m)$, ce qui est plus rapide que les précédents algorithmes connus, le meilleur d'entre eux prenant un temps en $O(m^2/\log ^2 m)$.

A new algorithm for the dense subset-sum problem is derived by using the structural characterization of the set of subset-sums obtained by analytical methods of additive number theory. The algorithm works for a large volume of summands $(m)$ with values that are bounded from above. The bound $(\ell )$ moderately depends on $m$. The new algorithm has $O(m^{7/4}/\log ^{3/4} m)$ time boundary that is faster than the previously known algorithms the best of which yields $O(m^2/\log ^2 m)$.

Analytical Number Theory, Integer Programming, Subset Sum Problem


Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...