The main objective of this text is to provide a comprehensive overview of results related to the group minimization problem on a finite Abelian group, also known as the Gomory group minimization problem, and its applications in integer linear programming, combinatorial optimization, and enumerative combinatorics. Significant attention is also given to the problem of computing the generalized convolution of two vectors, as the most advanced and efficient algorithms for solving the group minimization problem heavily rely on convolution computations. From the perspective of applications, particular emphasis is placed on Gomory’s asymptotic algorithm, the integer linear programming problem on the generalized hypercube, and the integer feasibility problem in a simplex.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Gomory Group Minimization Problem and Its Applications

  • Dmitry Gribanov,
  • Dmitry Malyshev

摘要

The main objective of this text is to provide a comprehensive overview of results related to the group minimization problem on a finite Abelian group, also known as the Gomory group minimization problem, and its applications in integer linear programming, combinatorial optimization, and enumerative combinatorics. Significant attention is also given to the problem of computing the generalized convolution of two vectors, as the most advanced and efficient algorithms for solving the group minimization problem heavily rely on convolution computations. From the perspective of applications, particular emphasis is placed on Gomory’s asymptotic algorithm, the integer linear programming problem on the generalized hypercube, and the integer feasibility problem in a simplex.