We consider in this paper the problem of finding optimal CAS's for incomplete AS's. The paper introduces some notions including the connected-super-forbidden-family and the lower-forbidden-family for AS's. We show that an optimal CAS can be derived from some smaller sized BIP whose variables (constraints, resp.) are based on the connected-super-forbidden-family (lower-forbidden-family, resp.) of the given AS. The paper further builds the close relationship between the problem of finding optimal CAS's and the set covering problem (SCP). We prove that the problem of finding a CAS with minimum cardinality of the primitive share set (or minimum average information rate) is equivalent to the SCP, and thus is NP-hard. Other contributions of the paper include: 1) two types of AS's are recognized so that we can construct the corresponding optimal CAS's directly; and 2) a greedy algorithm is proposed to find CAS's with smaller worst information rate.
Category / Keywords: Cumulative assignment scheme, Incomplete access structure, Set covering problem, NP-Hard Date: received 1 May 2012 Contact author: qiangl at sjtu edu cn Available formats: PDF | BibTeX Citation Version: 20120503:095346 (All versions of this report) Discussion forum: Show discussion | Start new discussion