On abstract integral dependence

On abstract integral dependence

0.00 Avg rating0 Votes
Article ID: iaor1990233
Country: United States
Volume: 14
Issue: 4
Start Page Number: 626
End Page Number: 638
Publication Date: Nov 1989
Journal: Mathematics of Operations Research
Authors: ,
Keywords: programming: integer
Abstract:

The concept of a tag system is introduced. In its general form the combinatorial structure of a dual pair of tag systems arises through composition of blocking pairs of clutters. This leads to a ‘painting’ characterization for dual pairs of tag systems which is useful for establishing combinatorial theorems of the alternative for certain classes of tag systems. Integral tag systems arise as a natural combinatorial abstraction of integral linear dependence properties of rational vectors in analogy with the manner in which matroids arise from linear dependence properties. Tag systems subsume matroids and several characterizations of matroids as tag systems are given; however, tag systems are shown to be generally less tractable computationally than matroids by establishing NP-completeness for the problem of determining a smallest base for an integral tag system.

Reviews

Required fields are marked *. Your email address will not be published.