Infinite Lexicographic Products of Triangular Algebras

Some new connections are given between linear orderings andtriangular operator algebras. A lexicographic product is dennedfor triangular operator algebras, and the Jacobson radical ofan infinite lexicographic product of upper triangular matrixalgebras is determined.     

Symmetrized-lexicographic order and the method of points

A variant of lexicographic order called symmetrized-lexicographic order is defined. The symmetrized-lexicographic order finds its application in the goal programming procedure called the method of points. The symmetrized-lexicographic order is shown to be representable using linear algebra and, thus, the method of points can be implemented as a linear programming problem.     

The nucleolus is well-posed

The lexicographic order is not representable by a real-valued function, contrary to many other orders or preorders. So, standard tools and results for well-posed minimum problems cannot be used. We prove that under suitable hypotheses it is however possible to guarantee the well-posedness of a lexicographic minimum over a compact or convex set. This result allows us to prove that some game theoretical solution concepts, based on lexicographic order are well-posed: in particular, this is true for the nucleolus.     

Lexicographic product decompositions of half linearly ordered loops

In this paper we prove for an hl-loop Q an assertion analogous to the result of Jakubík concerning lexicographic products of half linearly ordered groups. We found conditions under which any two lexicographic product decompositions of an hl-loop Q with a finite number of lexicographic factors have isomorphic refinements.     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

Generalized Derivatives of Lexicographic Linear Programs

Lexicographic linear programs are fixed-priority multiobjective linear programs that are a useful model of biological systems using flux balance analysis and for goal-programming problems. The objective function values of a lexicographic linear program as a function of its right-hand side are nonsmooth. This work derives generalized derivative information for lexicographic linear programs using lexicographic directional derivatives to obtain elements of the Bouligand subdifferential (limiting Jacobian). It is shown that elements of the limiting Jacobian can be obtained by solving related linear programs. A nonsmooth equation-solving problem is solved to illustrate the benefits of using elements of the limiting Jacobian of lexicographic linear programs.     

Some results on the lexicographic product of vertex-transitive graphs

Many large graphs can be constructed from existing smaller graphs by using graph operations, for example, the Cartesian product and the lexicographic product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the lexicographic products of vertex-transitive and of edge-transitive graphs. In particular, we show that the lexicographic product of Cayley graphs is a Cayley graph.     

Multiplicative representation of bilinear operators

We establish that each lattice bimorphism from the Cartesian product of two vector lattices into a universally complete vector lattice is representable as the product of two lattice homomorphisms defined on the factors. This fact makes it possible to reduce the problem to the linear case and obtain some results on representation of an order bounded disjointness preserving bilinear operator as a strongly disjoint sum of weighted shift or multiplicative operators.     

Block Orderings for Tensor-Product Grids in Two and Three Dimensions

We consider two-line and two-plane orderings for a convection–diffusion model problem in two and three dimensions, respectively. These strategies are aimed at introducing dense diagonal blocks, at the price of a slight increase of the bandwidth of the matrix, compared to natural lexicographic ordering. Comprehensive convergence analysis is performed for the block Jacobi scheme. We then move to consider a two-step preconditioning technique, and analyze the numerical properties of the linear systems that are solved in each step of the iterative process. For the 3-dimensional problem this approach is a viable alternative to the Incomplete LU approach, and may be easier to implement in parallel environments. The analysis is illustrated and validated by numerical examples.     

Mathematical morphology on bipolar fuzzy sets: general algebraic framework

In many domains of information processing, bipolarity is a core feature to be considered: positive information represents what is possible or preferred, while negative information represents what is forbidden or surely false. If the information is moreover endowed with vagueness and imprecision, as is the case for instance in spatial information processing, then bipolar fuzzy sets constitute an appropriate knowledge representation framework. In this paper, we focus on mathematical morphology as a tool to handle such information and reason on it. Applying mathematical morphology to bipolar fuzzy sets requires defining an appropriate lattice. We extend previous work based on specific partial orderings to any partial ordering leading to a complete lattice. We address the case of algebraic operations and of operations based on a structuring element, and show that they have good properties for any partial ordering, and that they can be useful for processing in particular spatial information, but also other types of bipolar information such as preferences and constraints. Particular cases using Pareto and lexicographic orderings are illustrated. Operations derived from fuzzy bipolar erosion and dilation are proposed as well.     

A lexicographic path order with slow growing derivation bounds

This paper is concerned with implicit computational complexity of the exptime computable functions. Modifying the lexicographic path order, we introduce a path order EPO. It is shown that a termination proof for a term rewriting system via EPO implies an exponential bound on the lengths of derivations. The path order EPO is designed so that every exptime function is representable as a term rewrite system compatible with EPO (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The jump number of suborders of the power set order

Let P be an ordered set induced by several levels of a power set. We give a formula for the jump number of P and show that reverse lexicographic orderings of P are optimal. The proof is based on an extremal set result of Frankl and Kalai.     

S/P images of upper triangular M-matrices

Preconditioning by approximate factorizations is widely used in iterative methods for solving linear systems such as those arising from the finite element formulation of many engineering problems. The influence of the ordering of the unknowns on their convergence behaviour has been the subject of recent investigations because of its particular relevance for the parallel implementation of these methods. Consistent orderings are attractive for parallel implementations and subclasses of these orderings have been shown to also enhance the convergence properties of the associated preconditioned iteration scheme. The present contribution is concerned with one such class of orderings, called S/P consistent orderings. More precisely, we review here their known properties and we propose a new definition which enlarges their scope of application. A device, called S/P image of an upper triangular M-matrix, provides a criterion for checking S/P consistency and a means to compute a relevant parameter, called maximal reduction ratio. All known properties of S/P consistent orderings are generalized to the new definition.     

Unretractive and S-unretractive joins and lexicographic products of graphs

Graphs without proper endomorphisms are the subject of this article. It is shown that the join of two graphs has this property if and only if both summands have it, and that the lexicographic product of a complete graph or an odd circuit as first factors has this property if and only if the second factor has it. A somewhat stronger theorem is proved if the lexicographic product has no proper strong endomorphism. The corresponding result for the join is the same as for usual endomorphisms.     

Ellipsoidal mixed-integer representability

Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using additional variables, by these systems are called ellipsoidal mixed-integer representable. In this work, we give geometric conditions that characterize ellipsoidal mixed-integer representable sets.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.     

An Interactive Multiple Criteria Approach to Ranking Alternatives

In this paper we are concerned with ranking various orderings of a set of alternatives to a composite order as a multiple criteria problem. The orderings (called preference orderings) can be real preference orderings or any natural orderings. The objective is to find the most preferred order of the decision maker using the preference orderings as criteria.In principle, the problem can be formulated as a multiple objective linear programming problem using the model of Bowman and Colantoni and then solved with the interactive method proposed by Zionts and Wallenius. However, the fact that we are dealing with integer variables prohibits us from applying this approach as such. We discuss the problem formulation and propose a modified approach to that of Zionts and Wallenius for solving the problem.     

A 3-approximation for the pathwidth of Halin graphs

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.