The greedy algorithm for partially ordered sets

Those independence systems on finite partially ordered sets are characterized for which the greedy algorithm always works.     

On a universal best choice algorithm for partially ordered sets

For the only known universal best choice algorithm for partially ordered sets with known cardinality and unknown order (proposed by J. Preater) we improve the estimation of the lower bound of its chance of success from the hitherto known constant 1/8 to 1/4. We also show that this result is the best possible for this algorithm, i.e., the 1/4 bound cannot be further improved. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

An analysis of the greedy algorithm for partially ordered sets

The worst-case analysis of the greedy algorithm for a combinatorial problem of linear maximization on a partially ordered set (introduced by U. Faigle [3]) is given.     

An enhanced ordered weighted averaging operators generation algorithm with applications for multicriteria decision making

In the present paper, we demonstrate that the degree of orness, which measures the attitudes of decision-makers, does not decrease strictly with the fractile values when either the normal probability density function or its inverse form is used to generate the weights of ordered weighted averaging operators. As for the weights of ordered weighted averaging operators generated from either the exponential distribution and its inverse form, we prove the strict monotonicity of the orness function with respect to the distribution shape parameter. To solve the drawbacks of the probability-density-function-based weight generation approach, the present paper uses the interweaving method to adjust the probability-density-function-based weighting vector of an ordered weighted averaging operator based on the premise that the distribution shape parameter is excluded. This enhanced approach retains the preferences of decision-makers to the utmost when they change their attitudes toward objects. Finally, the feasibility and effectiveness of this novel paradigm for generating the weights of ordered weighted averaging operators are demonstrated with its promising application in a system for aggregating movie ratings.     

Searching for partially ordered structures

General methods are developed to search for minimal and dead-end payoff operators for a class of sources endowed with a partial order structure. It is shown that the results can be used in the design of experiments with automata and in the minimization of Boolean functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 2, pp. 253–260, February, 1992.     

Completions for partially ordered semigroups

A standard completion γ assigns a closure system to each partially ordered set in such a way that the point closures are precisely the (order-theoretical) principal ideals. If S is a partially ordered semigroup such that all left and all right translations are γ-continuous (i.e., Y∈γS implies {x∈S:y·x∈Y}∈γS and {x∈S:x·y∈Y}∈γS for all y∈S), then S is called a γ-semigroup. If S is a γ-semigroup, then the completion γS is a complete residuated semigroup, and the canonical principal ideal embedding of S in γS is a semigroup homomorphism. We investigate the universal properties of γ-semigroup completions and find that under rather weak conditions on γ, the category of complete residuated semigroups is a reflective subcategory of the category of γ-semigroups. Our results apply, for example, to the Dedekind-MacNeille completion by cuts, but also to certain join-completions associated with so-called “subset systems”. Related facts are derived for conditional completions. A first draft of this paper by the second author, containing parts of Section 2, was received on August 9, 1985.     

A construction for partially ordered sets

A construction I(S) is defined which corresponds to the intuitive notion of the set of places in which new elements can be inserted into a given poset S. It is given the minimal possible ordering. It turns out that if the base sets are chains the construction produces the corresponding interval orders. for whose dimensions there exist good estimates. In this paper we make the dual restriction that the height of the underlying set is ?1. Under this assumption we find a bound for the dimension of I(S) in general and a precise value if the set consists of two antichains all the elements of one lying above all those of the other.     

A partition relation for partially ordered sets

We introduce a partition relation which is an alternate for measuring how badly the ordinary partition relation fails, we develop its corresponding partition calculus and we determine its status for various typical partially ordered sets.     

Quasimartingales on partially ordered sets

The concept of a quasimartingale, and therefore also of a function of bounded variation, is extended to processes with a regular partially ordered index set V and with values in a Banach space. We show that quasimartingales can be described by their associated measures, defined on an inverse limit space $\text{S × Ω}$ containing $\text{V × Ω}$, furnished with the σ-algebra $\text{P}$ of the predictable sets. With the help of this measure, a Rao-Krickeberg and a Riesz decomposition is obtained, as well as a convergence theorem for quasimartingales. For a regular quasimartingale X it is proven that the spaces ($\text{S × Ω}$, $\text{P}$) and the measures associated with X are unique up to isomorphisms. In the case V = $\text{R}$₊ⁿ we prove a duality between classical (right-) quasimartingales and left-quasimartingales.     

Nielsen fixed point theory for partially ordered sets

In this paper, we introduce a Nielsen type number for any selfmap f of a partially ordered set of spaces. This Nielsen theory relates to various existing Nielsen type fixed point theories for different settings such as maps of pairs of spaces, maps of triads, fibre preserving maps, equivariant maps and iterates of maps, by exploring their underlying poset structures.     

A cofinal coloring theorem for partially ordered algebras

If P is a directed partially ordered algebra of an appropriate sort-e.g. an upper semilattice-and has no maximal element, then P has two disjoint subalgebras each cofinal in P. In fact, if P has cofinality then there exists a family of such disjoint subalgebras. A version of this result is also proved without the directedness assumption, in which the cofinality of P is replaced by an invariant which we call its global cofinality.This work was done while the first author was partly supported by NSF contract MCS 82-02632.     

Fixed point for set-valued mappings satisfying an implicit relation in partially ordered metric spaces

Let (X,?) be a partially ordered set and d be a complete metric on X. Let F,G be two set-valued mappings on X. We obtained sufficient conditions for the existence of common fixed point of F and G satisfying an implicit relation in partially ordered set X.