Name
Title | ||
|---|---|---|
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2. |
Abstract | ||
|---|---|---|
We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy's additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain additivity relations. (2) We study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. (3) We give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under the assumption of a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function. |
Year | Venue | Field |
|---|---|---|
2014 | Math. Program. | Discrete geometry,Diagonal,Discrete mathematics,Infinite group,Mathematical optimization,Equivariant map,Cauchy distribution,Regular solution,Piecewise linear function,Functional equation,Mathematics |
DocType | Volume | Issue |
Journal | abs/1403.4628 | 1-2 |
Citations | PageRank | References |
8 | 0.51 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amitabh Basu | 1 | 331 | 27.36 |
| Robert Hildebrand | 2 | 69 | 7.82 |
| Matthias KöPpe | 3 | 191 | 20.95 |