Catalogue et commandes en ligne (paiement sécurisé, VISA ou MASTERCARD uniquement)

Revues disponibles par abonnement

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

Séries de livres

Astérisque

Cours Spécialisés

Documents Mathématiques

Mémoires de la SMF

Panoramas et Synthèses

Séminaires et Congrès

Série Chaire Jean Morlet

SMF/AMS Texts and Monographs

La Série T

Fascicules « Journée Annuelle »

Autres livres

Donald E. Knuth - traductions françaises

Rééditions du Séminaire Nicolas Bourbaki

Rééditions des Œuvres de Jean Leray

Revue de l'Institut Elie Cartan

Editions électroniques

Annales scientifiques de l'ENS

Bulletin de la SMF

Revue d'Histoire des Mathématiques

Séminaires et Congrès

Plus d'information / Abonnement

Publications grand 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

Pour les auteurs

Soumission des manuscrits

Formats et documentation

Plus d'info

Liste de diffusion électronique (smf.emath.fr)

Information pour les libraires et diffuseurs (smf.emath.fr)

Publications de la SMF
fr en
Votre numéro IP : 54.163.39.19
Accès aux édit. élec. : SémCong

Astérisque

Présentation de la publication

Parutions

Dernières parutions

Comité de rédaction / Secrétariat

Année :
Volume :

Faire une recherche


Catalogue & commande

Astérisque - Parutions - 1999 - 258 - pages 341-362

Parutions1999258

Structure Theory of Set Addition
Jean-Marc Deshouillers, Bernard Landreau, Alexander A. Yudin (Ed.)
Astérisque 258 (1999), 458 pages
Acheter l'ouvrage

New Structural Approach to Integer Programming: a Survey
Mark Chaimovich
Astérisque 258 (1999), 341-362

Résumé :
Cet article de synthèse présente un nouvel abord de la programmation entière basée sur la caractérisation de configurations extrêmes en théorie additive des nombres. La structure de ces configurations extrêmes nous permet d'élaborer des algorithmes applicables à des familles suffisamment larges de problèmes; ces algorithmes améliorent notablement les bornes actuellement connues. Là où ils sont applicables, ces algorithmes sont polynômiaux voire linéaires; c'est en particulier le cas pour les problèmes de type sac à dos. Pour cette classe de problèmes, l'amélioration sur les algorithmes antérieurs est d'au moins de deux ordres de grandeur.

Abstract:
The survey discusses a new approach to Integer Programming which is based on the structural characterization of problems using methods of additive number theory. This structural characterization allows one to design algorithms which are applicable in a narrower, yet still wide, domain of problems, and substantially improve the time boundary of existing algorithms. The new algorithms are polynomial for the class of problems in which they are applicable, and even linear (O(m)) for a wide class of the Subset-Sum and Value-Independent Knapsack problems. Previously known polynomial time algorithms for the same classes of problems are at least two orders of magnitude slower.

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

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


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