Strong duality for a special class of integer programs |
| |
Authors: | R. R. Meyer J. M. Fleisher |
| |
Affiliation: | (1) Computer Sciences Department, University of Wisconsin, Madison, Wisconsin;(2) Madison Academic Computing Center, University of Wisconsin, Madison, Wisconsin |
| |
Abstract: | A pair of primal-dual integer programs is constructed for a class of problems motivated by a generalization of the concept of greatest common divisor. The primal-dual formulation is based on a number-theoretic, rather than a Lagrangian, duality property; consequently, it avoids the dualitygap common to Lagrangian duals in integer programming.This research was partially supported by the National Science Foundation, Grant No. DCR-74-20584 |
| |
Keywords: | Integer programming duality Euclidean algorithm greatest common divisor primal-dual formulations |
本文献已被 SpringerLink 等数据库收录! |
|