Integer packing sets form a well-quasi-ordering

2019/11/28 by Alberto Del Pia, Dion Gijswijt, Del Pia, Alberto +5
Computer Science · Mathematics · #Optimization and Variational Analysis #Advanced Topology and Set Theory #Advanced Optimization Algorithms Research

paper · pdf · doi:10.48550/arxiv.1911.12841

Abstract

An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y ≤ x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in any packing polyhedron is an integer packing set. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a question recently posed by Bodur et al. In fact, we prove that the k-aggregation closure of any packing polyhedron is again a packing polyhedron. The generality of our main result allows us to provide a generalization to non-polyhedral sets: The k-aggregation closure of any downset of ℝⁿ₊ is a packing polyhedron.

Citations

• Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime Factors

Related

• The Aggregation Closure is Polyhedral for Packing and Covering Integer Programs
• One-Dimensional Packing: Maximality Implies Rationality
• Aggregation-based cutting-planes for packing and covering integer\n programs
• Dense packing of space with various convex solids
• The k-aggregation Closure for Covering Sets