Minimizing bumps in linear extensions of ordered sets
Given a finite partially ordered set P, there are many ways of imbedding the set into a linearly ordered one respecting order. Whenever \(a<b\), but a is incomparable to b in the original order, one speaks of a jump. Up to the present there is no known efficient algorithm to linearly extend a poset, minimizing the number of jumps. It seems to be known that determining the so-called jump number, i.e. the minimal number of jumps that must occur in any linearization, is NP-complete [W. R. Pulleyblank (to appear)]. The paper under review takes the opposite point of view by calling a bump an occurrence of \(a<b\), with \(a<b\) also in the original order. The problem is now to minimize bumps, which is equivalent to maximize jumps. (The puns involved in this choice of words are unfortunate, as they could never be translated into another language.) The authors study some possible algorithms for this problem. As in the case of the first problem, there are always some sufficient conditions on posets to guarantee optimality, but no necessary ones seem to be known.
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques
- Examples of Jump-Critical Ordered Sets
- Greedy linear extensions to minimize jumps
- scientific article; zbMATH DE number 3409103 (Why is no real title available?)
- Interval graphs and interval orders
- Jump number problem: The role of matroids
- Minimizing setups in ordered sets of fixed width
- Minimizing the jump number for partially ordered sets: A graph-theoretic approach
- On finding the jump number of a partial order by substitution decomposition
- On the size of jump-critical ordered sets
- Optimal Linear Extensions by Interchanging Chains
- Semiorders and a Theory of Utility Discrimination
- Greedy linear extensions to minimize jumps
- Greedy linear extensions for minimizing bumps
- Greedy posets for the bump-minimizing problem
- Computing the bump number is easy
- Computing the bump number with techniques from two-processor scheduling
- Minimizing bumps for posets of width two
- Minimizing bumps in ordered sets by substitution decomposition
- The jump number of Z-free ordered sets
- The setup polyhedron of series-parallel posets
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
- Generating linear extensions of posets by transpositions
- Minimizing the maximum bump cost in linear extensions of a poset
- scientific article; zbMATH DE number 27746 (Why is no real title available?)
- scientific article; zbMATH DE number 221764 (Why is no real title available?)
- scientific article; zbMATH DE number 800166 (Why is no real title available?)
- Minimizing the sum cost in linear extensions of a poset
- The connection between the bump number problem and flow-shop scheduling with precedence constraints
This page was built for publication: Minimizing bumps in linear extensions of ordered sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077441)
