A 3/2-approximation algorithm for the jump number of interval orders

The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number problem is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number.The complexity status for interval orders still remains unknown. Here we present a heuristic that, given an interval order P, generates a linear extension , whose jump number is less than 3/2 times the jump number of P.This work was supported by the Deutsche Forschungsgemeinschaft (DFG).     

Computing the bump number is easy

The bump number b(P) of a partial order P is the minimum number of comparable adjacent pairs in some linear extension of P. It has an interesting application in the context of linear circuit layout problems. Its determination is equivalent to maximizing the number of jumps in some linear extension of P, for which the corresponding minimization problem (the jump number problem) is known to be NP-hard. We derive a polynomial algorithm for determining b(P). The proof of its correctness is based on a min-max theorem involving simple-structured series-parallel partial orders contained in P. This approach also leads to a characterization of all minimal partial orders (with respect to inclusion of the order relations) with fixed bump number.Supported by Sonderforschungsbereich 303 of the University of Bonn.Supported by DAAD and SSHRC, Grant No. 451861295.     

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.     

An Optimal Algorithm to Find the Jump Number of Partially Ordered Sets

The jump number of a partially ordered set (poset) P isthe minimum number of incomparable adjacent pairs (jumps) in some linearextension of P. The problem of finding a linear extension of Pwith minimum number of jumps (jump number problem) is known to beNP-hard in general and, at the best of our knowledge, no exactalgorithm for general posets has been developed. In this paper, wegive examples of applications of this problem and propose for thegeneral case a new heuristic algorithm and an exactalgorithm. Performances of both algorithms are experimentallyevaluated on a set of randomly generated test problems.     

The Arboreal Jump Number of an Order

Let ${\mathcal P}$ be a partial order and ${\mathcal A}$ an arboreal extension of it (i.e. the Hasse diagram of ${\mathcal A}$ is a rooted tree with a unique minimal element). A jump of ${\mathcal A}$ is a relation contained in the Hasse diagram of ${\mathcal A}$ , but not in the order ${\mathcal P}$ . The arboreal jump number of ${\mathcal A}$ is the number of jumps contained in it. We study the problem of finding the arboreal extension of ${\mathcal P}$ having minimum arboreal jump number—a problem related to the well-known (linear) jump number problem. We describe several results for this problem, including NP-completeness, polynomial time solvable cases and bounds. We also discuss the concept of a minimal arboreal extension, namely an arboreal extension whose removal of one jump makes it no longer arboreal.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

Computing the bump number with techniques from two-processor scheduling

Let (X, <) be a partially ordered set. A linear extension x ₁, x ₂, ... has a bump whenever x _i<x _i+1, and it has a jump whenever x _iand x _i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem.Part of this work was done while the first author was a Research Student Associate at IBM Almaden Research Center. During the academic year his work is primarily supported by a Fannie and John Hertz Foundation Fellowship and is supported in part by ONR contract N00014-85-C-0731.     

Lie-trotter product formulas for nonlinear filtering

The nonlinear filtering problem for a diffusion process whose drift and diffusion coefficients depend parametrically on a finite-state jump process involves the solution of a vector system of linear, stochastic partial differential equations. A Lie-Trotter product formula is proven to hold for this system and a recursive implementation is discussed.     

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

Chain Dominated Orders

We study finite partial orders which have a chain such that every element of the order either belongs to this chain or has all its covers in this chain. We show that such orders are exactly the orders being both interval orders and truncated lattices. We prove that their jump number is polynomially tractable and that their dimension is unbounded. We also show that every order admits a visibility model having such an order as host.     

Generalization of the Neumann problem to harmonic functions outside cuts on the plane

We consider a boundary value problem for harmonic functions outside cuts on the plane. The jump of the normal derivative and a linear combination of the normal derivative on one side with the jump of the unknown function are given on each cut. The problem is considered with three conditions at infinity, which lead to distinct results on the existence and number of solutions. We obtain an integral representation of the solution in the form of potentials whose density satisfies a uniquely solvable Fredholm integral equation of the second kind.     

Optimal stationary control for dynamic systems with Markov perturbations

Affine continuous and discrete-time dynamic systems with homogeneous jump Markov perturbations are considered and the existence of an optimal stationary control under a quadratic cost is discussed. In order to solve this problem some new stability results for linear systems with Markov perturbations are given.     

A Simple Proof of Suzumura's Extension Theorem for Finite Domains With Applications

In this paper we provide a simple proof of the extension theorem for partial orderings due to Suzumura [1983] when the domain of the partial order is finite. The extension theorem due to Szpilrajn [1930] follows from this theorem. Szpilrajns extension theorem is used to show that an asymmetric binary relation is contained in the asymmetric part of a linear order if and only if it is acyclic. This theorem is then applied to prove three results. Finally we introduce the concept of a threshold choice function, and our third result says that such choice functions are the only ones to satisfy a property called functional acyclicity.     

Genetic Algorithm for the Jump Number Scheduling Problem

This paper introduces genetic algorithms for the jump number scheduling problem. Given a set of tasks subject to precedence constraints, the problem is to construct a schedule to minimize the number of jumps. We show that genetic algorithms outperform the previously known Knuth and Szwarcfiter's exhaustive search algorithm when applied to some classes of orders in which no polynomial time algorithms exist in solving the jump number problem. Values for various parameters of genetic jump number algorithms are tested and results are discussed.     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

An analytical approach to the unified solution of kinetic equations in the rarefied gas dynamics. II. Heat transfer problems

The ADO method, an analytical version of the discrete-ordinates method, is used here to solve a heat-transfer problem in a rarefied gas confined in a channel, as well as to solve a half-space problem in order to evaluate the temperature jump at the wall. This work is an extension of a previous work, devoted to flow problems, where the complete development of the solution, which is analytical in terms of the spatial variable, is presented in a way, such that, a wide class of kinetic models are considered, in an unified approach. A series of numerical results are showed and different simulations are used in order to establish a general comparative analysis based on this consistent set of results provided by the same methodology. In particular, numerical results for heat-flow profile, temperature and density perturbations are obtained for channels (walls), defined by different materials, on which different temperatures are imposed.     

An analytical approach to the unified solution of kinetic equations in the rarefied gas dynamics. II. Heat transfer problems

The ADO method, an analytical version of the discrete-ordinates method, is used here to solve a heat-transfer problem in a rarefied gas confined in a channel, as well as to solve a half-space problem in order to evaluate the temperature jump at the wall. This work is an extension of a previous work, devoted to flow problems, where the complete development of the solution, which is analytical in terms of the spatial variable, is presented in a way, such that, a wide class of kinetic models are considered, in an unified approach. A series of numerical results are showed and different simulations are used in order to establish a general comparative analysis based on this consistent set of results provided by the same methodology. In particular, numerical results for heat-flow profile, temperature and density perturbations are obtained for channels (walls), defined by different materials, on which different temperatures are imposed.     

On a generalization of the Neumann problem for the Laplace equation outside cuts in a plane

A boundary value problem for harmonic functions outside cuts in a plane is considered. The jump of the normal derivative is specified on the cuts as well as a linear combination of the normal derivative on one side of the cut and the jump of the unknown function. The problem is studied with three different conditions at infinity, which lead to different results on existence and number of solutions. The integral representation for a solution is obtained in the form of potentials density in which satisfies the uniquely solvable Fredholm integral equation of the 2nd kind. Copyright © 2004 John Wiley & Sons, Ltd.     

A primal-dual homotopy algorithm for $$\ell _{1}$$-minimization with $$\ell _{\infty }$$ℓ∞-constraints

In this paper we propose a primal-dual homotopy method for \(\ell _1\)-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.     

Extendability of Cyclic Orders

A cyclic order is a ternary relation that satisfies ternary transitivity and asymmetry conditions. Such a ternary relation is extendable if it is included in a complete cyclic order on the same ground set. Unlike the case of linear extensions of partial orders, a cyclic order need not be extendable. The extension problem for cyclic orders is to determine if a cyclic order is extendable. This problem is known to be NP-complete. We introduce a class of cyclic orders in which the extension problem can be solved in polynomial time. The class provides many explicit examples of nonextendable cyclic orders that were not previously known, including a nonextendable cyclic order on seven points. Let μ be the maximum cardinality of a ground set on which all cyclic orders are extendable. It has been shown that μ≤9. We prove that μ=6. This answers a question of Novák. In addition, we characterize the nonextendable cyclic orders on seven and eight points. Our results are intimately related to irreducible partially ordered set of order dimension three, and to fractional vertices of generalized transitive tournament polytopes. As by-products, we obtain a characterization of cyclically ordered sets of dimension two, and a new proof of a theorem of Dridi on small linear ordering polytopes. This revised version was published online in June 2006 with corrections to the Cover Date.