The monotone convergence theorem for multidimensional abstract Kurzweil vector integrals

We prove two versions of the Monotone Convergence Theorem for the vector integral of Kurzweil, , where R is a compact interval of , and f are functions with values on L(Z,W) and Z respectively, and Z and W are monotone ordered normed spaces. Analogous results can be obtained for the Kurzweil vector integral, , as well as to unbounded intervals R.     

On the size of maximal antichains and the number of pairwise disjoint maximal chains

Fix integers n and k with n≥k≥3. Duffus and Sands proved that if P is a finite poset and n≤|C|≤n+(n−k)/(k−2) for every maximal chain in P, then P must contain k pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if P is a finite poset and n≤|A|≤n+(n−k)/(k−2) for every maximal antichain in P, then P has k pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.     

An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

Order-couniversality of the complete infinitary tree: An application of zero-divisor graphs

Let

be the class of countably infinite bounded partially ordered sets

such that every non-minimum element of

has only finitely many successors, and has infinitely many immediate predecessors. Write

for the poset obtained by introducing maximum and minimum elements to the complete infinitary tree of nonempty finite sequences

of positive integers, where

if

is an extension of

. A poset

is called

-couniversal if

and for every

there is a bijective poset-homomorphism

. In this paper, couniversality is linked to zero-divisor graphs of partially ordered sets. It is proved that

is

-couniversal if and only if every non-maximum element of

is a (poset-theoretic) zero-divisor of

, and the zero-divisor graph of

is a spanning subgraph of the zero-divisor graph of

.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

偏序集的关联环的同构问题

设Ｘ是局部有限偏序集（或拟序集），Ｒ是含１的结合环，Ⅰ（Ｘ，Ｒ）是Ｒ上Ｘ的关联环，关联环的同构问题是指：问题１：怎样的环，能使环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｒ）推出偏序集之间的同构Ｘ芒Ｘ’？问题２：怎样的环或偏序集，能使环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｓ）推出Ｒ　Ｓ？本文证明了对唯一幂等元环（非交换），问题１有正面回答；对问题２，我们证明了对交换不可分解环Ｒ、Ｓ，由环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｒ）可得到Ｒ＝Ｓ，Ｘ＝Ｘ’。     

Can transitive orientation make sandwich problems easier?

A graph G_s=(V,E_s) is a sandwich for a pair of graphs G_t=(V,E_t) and G=(V,E) if E_t⊆E_s⊆E. A sandwich problem asks for the existence of a sandwich graph having an expected property. In a seminal paper, Golumbic et al. [Graph sandwich problems, J. Algorithms 19 (1995) 449-473] present many results on sub-families of perfect graphs. We are especially interested in comparability (resp., co-comparability) graphs because these graphs (resp., their complements) admit one or more transitive orientations (each orientation is a partially ordered set or poset). Thus, fixing the orientations of the edges of G_t and G restricts the number of possible sandwiches. We study whether adding an orientation can decrease the complexity of the problem. Two different types of problems should be considered depending on the transitivity of the orientation: the poset sandwich problems and the directed sandwich problems. The orientations added to both graphs G and G_s are transitive in the first type of problem but arbitrary for the second type.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Coupled fixed point results for mappings without mixed monotone property in partially ordered G-metric spaces

In this paper, we prove coupled fixed point results for mappings without mixed monotone property in partially ordered G-metric spaces. Also we showed that if $(X\text{,}G)$ is regular, these fixed point results holds.     

Combinatorial Criteria for Ramifiable Ordered Sets

The tree‐property (classica in cardina theory) and its variants make sense also for directed sets and even for partially ordered sets. A combinatoria approach is developed here, with characterizations and criteria involving (inter alia) adequate families of special substructures of directed sets. These substructures form a natural hierarchy that is also investigated.     

New monotone hybrid algorithm for hemi-relatively nonexpansive mappings and maximal monotone operators

The purpose of this article is to prove the strong convergence theorems for hemi-relatively nonexpansive mappings in Banach spaces. In order to get the strong convergence theorems for hemi-relatively nonexpansive mappings, a new monotone hybrid iteration algorithm is presented and is used to approximate the fixed point of hemi-relatively nonexpansive mappings. Noting that, the general hybrid iteration algorithm can be used for relatively nonexpansive mappings but it can not be used for hemi-relatively nonexpansive mappings. However, this new monotone hybrid algorithm can be used for hemi-relatively nonexpansive mappings. In addition, a new method of proof has been used in this article. That is, by using this new monotone hybrid algorithm, we firstly claim that, the iterative sequence is a Cauchy sequence. The results of this paper modify and improve the results of Matsushita and Takahashi, and some others.     

Duality between quasi-concave functions and monotone linkage functions

A function F defined on the family of all subsets of a finite ground set E is quasi-concave, if F(X∪Y)≥min{F(X),F(Y)} for all X,Y⊆E. Quasi-concave functions arise in many fields of mathematics and computer science such as social choice, graph theory, data mining, clustering and other fields. The maximization of a quasi-concave function takes, in general, exponential time. However, if a quasi-concave function is defined by an associated monotone linkage function, then it can be optimized by a greedy type algorithm in polynomial time. Recently, quasi-concave functions defined as minimum values of monotone linkage functions were considered on antimatroids, where the correspondence between quasi-concave and bottleneck functions was shown Kempner and Levit (2003) [6]. The goal of this paper is to analyze quasi-concave functions on different families of sets and to investigate their relationships with monotone linkage functions.     

On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators

This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefore, applications of Douglas—Rachford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new,generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.This paper is drawn largely from the dissertation research of the first author. The dissertation was performed at M.I.T. under the supervision of the second author, and was supported in part by the Army Research Office under grant number DAAL03-86-K-0171, and by the National Science Foundation under grant number ECS-8519058.     

Optimal and near-optimal mixed covering arrays by column expansion

This paper describes constructions for strength-2 mixed covering arrays developed from index-1 orthogonal arrays, ordered designs and covering arrays. The constructed arrays have optimal or near-optimal sizes. Conditions for achieving optimal size are described. An optimization among the different ingredient arrays to maximize the number of factors of each alphabet size is also presented.     

Accelerated projection-based forward-backward splitting algorithms for monotone inclusion problems

In this paper, based on inertial and Tseng''s ideas, we propose two projection-based algorithms to solve a monotone inclusion problem in infinite dimensional Hilbert spaces. Solution theorems of strong convergence are obtained under the certain conditions. Some numerical experiments are presented to illustrate that our algorithms are efficient than the existing results.     

Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts we seek to maximize . For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|,|T|}, where {S,T} is a partition of V(G)?C with s∈S, t∈T and [S,T]=0?, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.     

Distributive lattices of small width, II: A problem from Stanley's 1986 text Enumerative Combinatorics

In Richard P. Stanley's 1986 text, Enumerative Combinatorics, the following problem is posed: Fix a natural number k. Consider the posets P of cardinality n such that, for 0<i<n, P has exactly k order ideals (down-sets) of cardinality i. Let fk(n) be the number of such posets. What is the generating function ∑f₃(n)xn?In this paper, the problem is solved.     

A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems *

Several interior point algorithms have been proposed for solving nonlinear monotone complementarity problems. Some of them have polynomial worst-case complexity but have to confine to short steps, whereas some of the others can take long steps but no polynomial complexity is proven. This paper presents an algorithm which is both long-step and polynomial. In addition, the sequence generated by the algorithm, as well as the corresponding complementarity gap, converges quadratically. The proof of the polynomial complexity requires that the monotone mapping satisfies a scaled Lipschitz condition, while the quadratic rate of convergence is derived under the assumptions that the problem has a strictly complementary solution and that the Jacobian of the mapping satisfies certain regularity conditions     

Global linear convergence of a path-following algorithm for some monotone variational inequality problems

We consider a primal-scaling path-following algorithm for solving a certain class of monotone variational inequality problems. Included in this class are the convex separable programs considered by Monteiro and Adler and the monotone linear complementarity problem. This algorithm can start from any interior solution and attain a global linear rate of convergence with a convergence ratio of 1 ?c/√m, wherem denotes the dimension of the problem andc is a certain constant. One can also introduce a line search strategy to accelerate the convergence of this algorithm.