On-line catalogue and orders (secure paiement, VISA or MASTERCARD only)

Journals available by subscription

Annales scientifiques de l'ENS

Astérisque

Bulletin de la SMF

Mémoires de la SMF

Revue d'Histoire des Mathématiques

Gazette des Mathématiciens

Books

Astérisque

Cours Spécialisés

Documents Mathématiques

Mémoires de la SMF

Panoramas et Synthèses

Séminaires et Congrès

Jean Morlet Chair Series

SMF/AMS Texts and Monographs

La Série T

Volumes "Journée Annuelle"

Other Books

Donald E. Knuth - French translations

Nicolas Bourbaki's seminar new edition

Jean Leray's scientific works new edition

Revue de l'Institut Elie Cartan

Electronic Editions

Annales scientifiques de l'ENS

Bulletin de la SMF

Revue d'Histoire des Mathématiques

Séminaires et Congrès

More information / Subscription

Publications for a general public

L'explosion des mathématiques (smf.emath.fr)

Mathématiques L'explosion continue (smf.emath.fr)

Zoom sur les métiers des maths (smf.emath.fr)

Zoom sur les métiers des mathématiques et de l'informatique (smf.emath.fr)

Où en sont les mathématiques ?

La Série T

For the authors

Submission of manuscripts

Formats and documentation

More info

Electronic distribution list (smf.emath.fr)

Information for bookselers and subscription agencies (smf.emath.fr)

Publications de la SMF
fr en
Your IP number: 54.91.48.104
Access to elec. publ.: SémCong

Astérisque

Presentation of the publication

Titles

Last Titles

Editorial staff committee / Secretary

Year:
Number:

Search


Catalogue & orders

Astérisque - Titles - 1999 - 258 - pages 363-373

Titles1999258

Structure Theory of Set Addition
Jean-Marc Deshouillers, Bernard Landreau, Alexander A. Yudin (Ed.)
Astérisque 258 (1999), 458 pages
Buy the book

New Algorithm for Dense Subset-Sum Problem
Mark Chaimovich
Astérisque 258 (1999), 363-373

Résumé :
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)$.

Abstract:
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)$.

Key words: Analytical Number Theory, Integer Programming, Subset Sum Problem

Class. math. : Primary: 90C10 Alternate: 05A17, 11B25, 68Q25


ISSN : 0303-1179
Publié avec le concours de : Centre National de la Recherche Scientifique