On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem
| Autor: | Matthias Köppe, Robert Hildebrand, Yuan Zhou |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
050101 languages & linguistics
Rational number Pure mathematics Direct sum 05 social sciences 02 engineering and technology Linear subspace Piecewise linear function Inverse semigroup Infinite group Homogeneous space 0202 electrical engineering electronic engineering information engineering Equivariant map 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Mathematics |
| Zdroj: | Integer Programming and Combinatorial Optimization ISBN: 9783030179526 IPCO |
| Popis: | The non-extreme minimal valid functions for the Gomory–Johnson infinite group problem are those that admit effective perturbations. For a class of piecewise linear functions for the 1-row problem we give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The infinite-dimensional subspaces have partial symmetries; to describe them, we develop a theory of inverse semigroups of partial bijections, interacting with the functional equations satisfied by the perturbations. Our paper provides the foundation for grid-free algorithms for testing extremality and for computing liftings of non-extreme functions. The grid-freeness makes the algorithms suitable for piecewise linear functions whose breakpoints are rational numbers with huge denominators. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|