๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Computational Complexity of Antimatroid Properties

โœ Scribed by Jamas Enright

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
164 KB
Volume
26
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

โœฆ Synopsis

Oracle complexity for antimatroids is defined. Several antimatroid oracles are compared and their relative strengths are examined. Characterizations of several classes of antimatroids are given, and the complexity of recognising membership of these classes is examined.

๐Ÿ“œ SIMILAR VOLUMES

The Computational Complexity of Choice S
The Computational Complexity of Choice Sets
โœ Felix Brandt; Felix Fischer; Paul Harrenstein ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 136 KB

## Abstract Social choice rules are often evaluated and compared by inquiring whether they satisfy certain desirable criteria such as the __Condorcet criterion__, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of

The Computational Complexity of Densest
The Computational Complexity of Densest Region Detection
โœ Shai Ben-David; Nadav Eiron; Hans Ulrich Simon ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 296 KB

We investigate the computational complexity of the task of detecting dense regions of an unknown distribution from unlabeled samples of this distribution. We introduce a formal learning model for this task that uses a hypothesis class as it ''anti-overfitting'' mechanism. The learning task in our mo

The Computational Complexity of Some Pro
The Computational Complexity of Some Problems of Linear Algebra
โœ Jonathan F Buss; Gudmund S Frandsen; Jeffrey O Shallit ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 330 KB

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x 1 , x 2 , ..., x t be variables. Given a matrix M=M(x 1 , x 2 , ..., x t ) with entries chosen from E \_ [x 1 , x 2 , ..., x t ], we want to determine maxrank S (M)=