مشکل سهام اسکیبینگ و ارتباط آن با پیوند هیپرگراف

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of products with minimum length L that can be constructed by connecting a given supply of m∈N smaller item lengths l1,…,lm with availabilities b1,…,bm. For this NP-hard optimization problem, we investigate the quality of the proper relaxation by considering the proper gap, i.e., the difference between the optimal objective values of the proper relaxation and the skiving stock problem itself. In this regard, we introduce a theory to obtain the proper gap on the basis of hypergraph matchings. As a main contribution, we characterize those hypergraphs that belong to an instance of the skiving stock problem, and consider the special case of 2-uniform hypergraphs in more detail. Moreover, this particular class is shown to correspond one-to-one and onto a certain power set. Based on this result, the number of related non-isomorphic hypergraphs and their possible proper gaps can be calculated explicitly.