Abstract: Let ܥ be a collection of objects, characterized by the set ܣ = {ܽଵ,⋯,ܽ௡} of binary attributes. We consider problems of the following type: given an object-characterization table, it is to check if there exists a subset ܯ in ܥ of a given size, such that each attribute of A is satisfied by a given number of objects in ܯ. Additional restriction may be applied such as - the number of matches of each object in ܯ is limited. In this paper we investigate particular cases of the general problem, and consider approximation solutions by means of binary classification trees.

Keywords: Classification tree, covering, greedy algorithm.

ACM Classification Keywords: F.2.2 Nonnumerical Algorithms and Problems

Link:

CONSTRAINED OBJECT-CHARACTERIZATION TABLES AND ALGORITHMS1

Hasmik Sahakyan

http://www.foibg.com/ijicp/vol01/ijicp01-02-p04.pdf