Identification of Threshold, Regular and Submodular Monotone Systems: Theory and Algorithms

  • Boros, Endre (PI)
  • Khachiyan, Leonid (CoPI)
  • Gurvich, Vladimir A. (CoPI)

Project Details


The focus of this research is the development of algorithms, theory, and applications for the identification of all minimal representatives, for implicitly given monotone systems. Such systems are a frequent target of knowledge discovery as they represent important information hidden in large databases, complex networks, etc. Problems involving the determination of monotone systems arise naturally in a multitude of areas including: data mining (finding all maximal frequent, minimal infrequent sets); text mining (finding the best linear query in vector space models); machine learning (finding the best rules or patterns); hypergraph dualization (generating all minimal transversals); reliability theory (generating all minimal working and/or maximal failing states); integer programming (generating all minimal feasible solutions); stochastic programming (constructing deterministic equivalents to certain stochastic models); etc. A coherent theory of identification problems for monotone systems based on several recent mathematical results will be developed. Tractable classes will be outlined, efficient algorithms for such classes created and realized by programs. The resulting new methods will be tested on a variety of applications, such as data mining, logical data analysis, machine learning and text mining.

Effective start/end date12/1/0111/30/05


  • National Science Foundation: $354,297.00


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.