# Correspondence between two Antimatroid Algorithmic Characterizations

@article{Kempner2003CorrespondenceBT, title={Correspondence between two Antimatroid Algorithmic Characterizations}, author={Yulia Kempner and Vadim E. Levit}, journal={Electron. J. Comb.}, year={2003}, volume={10} }

The basic distinction between already known algorithmic characterizations of matroids and antimatroids is in the fact that for antimatroids the ordering of elements is of great importance. While antimatroids can also be characterized as set systems, the question whether there is an algorithmic description of antimatroids in terms of sets and set functions was open for some period of time. This article provides a selective look at classical material on algorithmic characterization of… Expand

#### Topics from this paper

#### 19 Citations

A Geometric Characterization of Poly-antimatroids

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2007

This research concentrates on interrelations between geometric, algorithmic, and lattice properties of poly-antimatroids. Expand

Two Characterizations of Antimatroids

- Mathematics
- 2013

Abstract NextClosure algorithm is a fast and good algorithm in formal concept analysis. With the assistance of NextClosure algorithm, this article provides a characterization of antimatroids.… Expand

Geometry of antimatroidal point sets

- Mathematics, Computer Science
- ArXiv
- 2008

This research focuses on geometrical properties of antimatroidal point sets in the plane and proves that these sets are exactly parallelogram polyominoes, implying that two-dimensional antimatroids have convex dimension 2. Expand

Poly-antimatroid polyhedra

- Mathematics, Computer Science
- Ars Math. Contemp.
- 2014

It is proved that the convex dimension of an n -dimensional poset poly-antimatroid is equal to n, which is the minimum number of maximal chains needed to realize S . Expand

Recognition of Antimatroidal Point Sets

- Mathematics, Computer Science
- Graph Theory, Computational Intelligence and Thought
- 2009

A set of corner points is defined that concisely represents a given antimatroidal point set and an algorithm is presented allowing the given set of points to be recognized as a set of Corner points of some antimatroids point set. Expand

Quasi-concave functions on antimatroids

- Mathematics, Computer Science
- 2004

The main finding is that quasi-concave set functions on an antimatroid may be represented as minimum values of some monotone linkage functions. Expand

Poly-Dimension of Antimatroids

- Mathematics
- 2012

A partial cube is a graph that can be isometrically embedded into a hypercube. In other words, a partial cube is a subgraph of a hypercube that preserves distances the distance between any two… Expand

0 Poly-Dimension of Antimatroids

- 2012

A partial cube is a graph that can be isometrically embedded into a hypercube. In other words, a partial cube is a subgraph of a hypercube that preserves distances the distance between any two… Expand

Quasi-concave functions on meet-semilattices

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2008

It is shown that the class of functions defined as minimum values of monotone linkage functions coincides with theclass of quasi-concave set functions, which means that such a set function can be maximized by a greedy type algorithm over a family of all subsets of a finite set. Expand

Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity

- Mathematics, Computer Science
- ArXiv
- 2021

This work provides a parallel algorithm with a time complexity over n processors of O(ng) + O(log log n) where n is the cardinality of the ground set and g is the complexity to compute the monotone linkage function that induces a corresponding quasi-concave set function via a duality. Expand

#### References

SHOWING 1-10 OF 14 REFERENCES

An algorithmic characterization of antimatroids

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1990

It is demonstrated that the properties of antimatroids are not only sufficient but necessary to solve the scheduling problem posed by Lawler, thus yielding an algorithmic characterization of antimuayids. Expand

Matroid Applications: Introduction to Greedoids

- Mathematics
- 1992

Introduction Greedoids were invented around 1980 by B. Korte and L. Lovasz. Originally, the main motivation for proposing this generalization of the matroid concept came from combinatorial… Expand

Axiomatizations of the Shapley value for cooperative games on antimatroids

- Mathematics, Computer Science
- Math. Methods Oper. Res.
- 2003

This paper establishes axioms that determine the restricted Shapley value on antimatroids by conditions on the cooperative game v and the structure determined by the antimatroid and provides an axiomatization of the Shapleyvalue restricted to the smaller class of poset antimatroid. Expand

Multiple sequence alignment using the quasi-concave function optimization based on the DIALIGN combinatorial structures

- Mathematics
- 2001

Multiple sequence alignment is usually considered as an optimization problem, which has a statistical and a structural component. It is known that in the problem of protein sequence alignment a… Expand

Incomplete classifications of a finite set of objects using Monotone Systems

- Mathematics
- 1989

The problem of incomplete classification is solved using a monotone system of a special kind. A classification method based on identification of the minimal cores of the monotone system is proposed.… Expand

Monotone Linkage Clustering and Quasi-Convex Set Functions

- Mathematics
- 1995

Selecting subsets with adding the elements one by one is implicitely employed in many heuristical clustering procedures. Such a procedure, seriation, can be described generally in terms of a linkage… Expand

Introduction to greedoids, in " Matroid applications

- Introduction to greedoids, in " Matroid applications
- 1992

Monotone linkage clustering and quasi-concave functions

- Appl.Math.Lett
- 1997

Monotone linkage clustering and quasiconcave functions

- Appl.Math.Lett
- 1997

Faigle An algorithmic characterization of antimatroids

- Discrete Applied Mathematics
- 1990