Modifications of object sizes and box capacities to achieve a simultaneous fitting

✍ Scribed by Oldřich Botlík

• Publisher: Elsevier Science
• Year: 1977
• Tongue: English
• Weight: 462 KB
• Volume: 18
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(77)90071-1

✦ Synopsis

Given a se: of k objects of positive integral si;lL:, (s,) and a set of n boxes of positive integral capacitks (b, 1 we define a compatibility relatioil between each box and some subset of obiects such that the condition s, s 6, is necessarv but not suflicient for object i to be compatible with I box i. A, sim~litaneous fitting of objects in boxes is one where every object is compatible to Its box and no b 3x has its capacity exceeded. In this paper, a necessary condition for the existence of such a fitting is stated. It is shown that this condition is sufficient for the existence of fittings under certain modifications of sizes or capacities. Two measures of the magnitude of the needed modification are introduced and lexamined.