Integer packing sets form a well-quasi-ordering
Alberto Del Pia (delpiawisc.edu)
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 R^n_+ is a packing polyhedron.
Keywords: Well-quasi-ordering; k-aggregation closure; Polyhedrality; Packing polyhedra.
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Entry Submitted: 01/31/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|