Trapezoid Order Classification

In this paper we show the nonequivalence of combinations of several natural geometric restrictions on trapezoid representations of trapezoid orders. Each of the properties unit parallelogram, unit trapezoid and proper parallelogram, unit trapezoid and parallelogram, unit trapezoid, proper parallelogram, proper trapezoid and parallelogram, proper trapezoid, parallelogram, and trapezoid is shown to be distinct from each of the others. Additionally, interval orders are shown to be both unit trapezoid and proper parallelogram orders.     

Free Triangle Orders

We define a new class of ordered sets, called free triangle orders. These are ordered sets represented by a left-to-right ordering on geometric objects contained in a horizontal strip in the plane. The objects are called 'free triangles', and have one vertex on each of the two boundaries of the strip and one vertex in its interior. These ordered sets generalize the classes of trapezoid and triangle orders studied by Bogart, Möhring, and Ryan, represented by trapezoids and triangles respectively, contained within a strip in the plane, and are a special case of the orders of tube dimension 2 introduced by Habib and co-workers, which are represented by any set of convex bodies contained within a strip in the plane. Our main result is that the class of free triangle orders strictly contains the class of trapezoid orders.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

Trapezoid graphs and their coloring

We define trapezoid graphs, an extension of both interval and permutation graphs. We show that this new class properly contains the union of the two former classes, and that trapezoid graphs are equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. We provide an optimal coloring algorithm for trapezoid graphs that runs in time O(nk), where n is the number of nodes and k is the chromatic number of the graph. Our coloring algorithm has direct applications to channel routing on integrated circuits.     

Triangle,Parallelogram, and Trapezoid Orders

In his 1998 paper, Ryan classified the sets of unit, proper, and plain trapezoid and parallelogram orders. We extend this classification to include unit, proper, and plain triangle orders. We prove that there are 20 combinations of these properties that give rise to distinct classes of ordered sets, and order these classes by containment.     

Completion of the mixed unit interval graphs hierarchy

We describe the missing class of the hierarchy of mixed unit interval graphs. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left‐closed‐right‐open. (By symmetry, considering closed, open, and right‐closed‐left‐open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic‐time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic‐time algorithm to recognize the class of mixed unit interval graphs.     

Tube Representations of Ordered Sets

We define the (n,i,f)-tube orders, which include interval orders, trapezoid orders, triangle orders, weak orders, order dimension n, and interval-order-dimension n as special cases. We investigate some basic properties of (n,i,f)-tube orders, and begin classifying them by containment. Mathematics Subject Classifications (2000) 06A06, 05C62.     

Optimal preemptive scheduling on a fixed number of identical parallel machines

In this paper, we consider the preemptive scheduling problem on a fixed number of identical parallel machines. We present a polynomial-time algorithm for finding a minimal length schedule for an order class which contains properly interval orders.     

Free mobility and taste-homogeneity of jurisdiction structures

We consider a population of agents distributed on the unit interval. Agents form jurisdictions in order to provide a public facility and share its costs equally. This creates an incentive to form large entities. Individuals also incur a transportation cost depending on their location and that of the facility which makes small jurisdictions advantageous. We consider a fairly general class of distributions of agents and generalize previous versions of this model by allowing for non-linear transportation costs. We show that, in general, jurisdictions are not necessarily homogeneous. However, they are if facilities are always intraterritory and transportation costs are superadditive. Superadditivity can be weakened to strictly increasing and strictly concave when agents are uniformly distributed.     

On Selections from the Best <Emphasis Type="Italic">n</Emphasis>-Nets

The discontinuity of any selection from a best n-net for n ≥ 2 in an arbitrary not strictly convex Banach space is proved. It is also proved that there is no Lipschitz selection on an arbitrary Banach space of dimension at least 2 whose unit sphere contains an attainable point of smoothness.     

Unit Interval Orders of Open and Closed Intervals

A poset P = (X, ?) is a unit OC interval order if there exists a representation that assigns an open or closed real interval I(x) of unit length to each x ∈ P so that x ? y in P precisely when each point of I (x) is less than each point in I (y). In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The algorithm takes a poset P as input and either produces a representation or returns a forbidden poset induced in P.     

Inductive Characterizations of Finite Interval Orders and Semiorders

We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class.     

A new adaptive Barzilai and Borwein method for unconstrained optimization

In this paper we view the Barzilai and Borwein (BB) method from a new angle, and present a new adaptive Barzilai and Borwein (NABB) method with a nonmonotone line search for general unconstrained optimization. In the proposed method, the scalar approximation to the Hessian matrix is updated by the Broyden class formula to generate an adaptive stepsize. It is remarkable that the new stepsize is chosen adaptively in the interval which contains the two well-known BB stepsizes. Moreover, for the negative curvature direction, a strategy for the choice of the stepsize is designed to accelerate the convergence rate of the NABB method. Furthermore, we apply the NABB method without any line search to strictly convex quadratic minimization. The numerical experiments show the NABB method is very promising.     

The perturbation classes problem in Fredholm theory

We give a negative answer to the perturbation classes problem: the perturbation class of the upper semi-Fredholm operators contains properly the strictly singular operators, and the perturbation class of the lower semi-Fredholm operators contains properly the strictly cosingular operators.     

Being a Proper Trapezoid Ordered Set Is a Comparability Invariant

It is proved that if we replace an autonomous subset of a finite proper trapezoid ordered set with a proper trapezoid ordered set, then we obtain a proper trapezoid ordered set provided the autonomous subset is not an antichain, and analogously in the k-dimensional case. As corollaries we obtain that being a proper trapezoid ordered set is a comparability invariant, more generally, proper interval dimension is a comparability invariant.     

On some new types of greedy chains and greedy linear extensions of partially ordered sets

Two new types of greedy chains, strongly and semi-strongly greedy, in posets are defined and their role in solving the jump number problem is discussed in this paper. If a poset P contains a strongly greedy chain C then C may be taken as the first chain in an optimal linear extension of P. If a poset P has no strongly greedy chains then it contains an optimal linear extension which starts with a semi-strongly greedy chain. Hence, every poset has an optimal linear extension which consists of strongly and semi-strongly greedy chains. Algorithmic issues of finding such linear extensions are discussed elsewhere (Syslo, 1987, 1988), where we provide a very efficient method for solving the jump number problem which is polynomial in the class of posets whose arc representations contain a bounded number of dummy arcs. In another work, the author has recently demonstrated that this method restricted to interval orders gives rise to 3/2-approximation algorithm for such posets.     

Gedämpfte zahlentheoretische Transformationen

Generalizing earlier work ofJ. Galambos and the present author a model of a class of transformations mapping the unit interval into itself is proposed. This class contains the classical series expansions of Sylvester and Engel, the algorithm of Pierce and a lot of their genralizations. The main result is an ergodic theorem: the space mean of a certain sequence equals the time mean almost every-where.     

ContributionsTree-visibility orders

We introduce a new class of partially ordered sets, called tree-visibility orders, containing interval orders, duals of generalized interval orders and height one orders. We give a characterization of tree-visibility orders by an infinite family of minimal forbidden suborders. Furthermore, we present an efficient recognition algorithm for tree-visibility orders.     

分段连续逐个迭代算法的研究及其在水库流域汇流计算中的应用

河流流域由降雨量与单位过程线所形成的出流过程的方程组呈菱形,可用赛德尔迭代法求解,而水库(湖泊)流域的净雨量与单位累积过程线所形成的水库(湖泊)入流过程的方程组呈梯形,不能用赛德尔迭代法,为此我们提出分段连续逐个迭代法,并通过实例计算,取得了很好的计算效果.