BazTech - Yadda

Ograniczanie wyników

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: posets

Sortuj według:

Ogranicz wyniki do:

The database of interval orders difficult for the jump number minimizing algorithms

Krysztowiak P.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2011

Vol. 11, no. 1

15-22

The problems of scheduling jobs on a single machine subject to precedence constraints can often be modelled as the jump number problem for posets, where a linear extension of a given partial order is to be found which minimizes the number of noncomparabilities. In this paper, we are investigating a restricted class of posets, called interval orders, admitting approximation algorithms for the jump number problem, in which the problem remains NP-complete. We have implemented three known approximation algorithms for this problem, all of which are guaranteed to produce solutions that are at most 50% worse than the optimal ones. More importantly, we have performed an exhaustive search for particularly hard interval orders, which enforce the algorithms to generate orderings which are exactly 50% worse than the optimal linear extensions. The main purpose of this paper is to present the database of those problematic posets.

Rings related to finite posets

Dokuchaev M., Gubareni N.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

2010

Vol. 9, nr 2

25-36

In this article we consider special classes of rings related to finite partially ordered sets over division rings and prime hereditary Noetherian rings. The structure and main properties of these rings are studied. These rings are closely connected with right hereditary SPSD-rings.

Ordered continuity structures and their relationship to topology

Leseberg D.

Demonstratio Mathematica

2002

Vol. 35, nr 1

175-197

Algebras associated with posets

Neggers J., Kim H. S.

Demonstratio Mathematica

2001

Vol. 34, nr 1

13-23

In this paper we introduce a class of algebras whose bases over a field K are pogroupoids. We discuss several properties of these algebras as they relate to the structure of their associated pogroupoids and through these to the associated posets also. In particular the Jacobi form is O precisely when the pogroupoid is a semigroup, precisely when the posets is (C2 + 1)-free. Thus, it also follows that a pg-algebra KS over a field K is a Lie algebra with respect to the commutator product iff its associated posets S(<) is (C2 +1)-free. The ideals generated by commutators have some easily identifiable properties m terms of the incomparability graph of the posets associated with the pogroupoid base of the algebra. We conjecture that a fundamental theorem on the relationship between isomorphic algebras and isomorphic pogroupoids holds as well.