Proceedings PaperDiscrete metrics as Gomory functions
|Format||Member Price||Non-Member Price|
It has been shown recently that discrete, non-decreasing subadditive functions are value functions of pure integer programs and so belong to the class of Gomory functions. Some consequences of this result for discrete metrics are reported in this paper. If a discrete metric in the digital plane is invariant under translations and reflections in the axes, then it is determined by a subadditive function on the first quadrant. If it is also non-decreasing in each coordinate then its values in each finite block are determined by a Gomory function. If the values of the function throughout the first quadrant are determined by the values in a finite block, either by shift-periodicity or by a Hilbert basis, then the subadditive function is determined in the whole of the first quadrant by a unique Gomory function.