SMF

New Structural Approach to Integer Programming: a Survey

New Structural Approach to Integer Programming: a Survey

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

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 e de problèmes, l'amélioration sur les algorithmes antérieurs est d'au moins de deux ordres de grandeur.

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 of problems in which they are applicable, and even linear ($O(m)$) for a wide of the Subset-Sum and Value-Independent Knapsack problems. Previously known polynomial time algorithms for the same es of problems are at least two orders of magnitude slower.

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...