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