A 3/2-approximation algorithm for the jump number of interval orders
Let P be a (partially) ordered finite set. A pair of two consecutive elements \(x_ i<x_{i+1}\) of a linear extension L of P is called a jump if \(x_ i\) is incomparable to \(x_{i+1}\) in P. The number of all jumps of L is denoted by \(s_ p(L)\). The minimum number of \(s_ P(L)\) is called the jump number s(P) of P \((s(P)=\min \{a_ P(L):\) L is a linear extension of \(P\}\)). An optimal linear extension L of P has the property \(s(P)=s_ P(L).\) In this paper some algorithms constructing linear extensions are developed, especially for interval orders, which are ordered sets P whose elements are in a one-to-one correspondence with intervals on the real axis \((x\leftrightarrow I_ x)\) such that \(x<_ Py\) iff sup \(I_ x\leq \inf I_ y\). For an interval order P a linear extension \(\Lambda\) is constructed with \(s_ P(\Lambda)\leq (3/2)s(P)\).
- An improved approximation ratio for the jump number problem on interval orders
- The jump number problem on interval orders: A 3/2 approximation algorithm
- Jump number maximization for proper interval graphs and series-parallel graphs
- scientific article; zbMATH DE number 19350
- Tackling the jump number of interval orders
- A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
- A setup heuristic for interval orders
- Algorithmic Approaches to Setup Minimization
- Minimizing Setups for Cycle-Free Ordered Sets
- 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 minimizing the jump number for interval orders
- Optimal Linear Extensions by Interchanging Chains
- On minimizing the jump number for interval orders
- On minimizing jumps for ordered sets
- Tackling the jump number of interval orders
- On a setup optimization problem for interval orders
- Computing the jump number on semi-orders is polynomial
- Jump number maximization for proper interval graphs and series-parallel graphs
- The jump number problem on interval orders: A 3/2 approximation algorithm
- The arboreal jump number of an order
- A refined analysis on the jump number problem of interval orders
- An improved approximation ratio for the jump number problem on interval orders
- scientific article; zbMATH DE number 19350 (Why is no real title available?)
- scientific article; zbMATH DE number 764417 (Why is no real title available?)
- A tabu search approach to the jump number problem
This page was built for publication: A 3/2-approximation algorithm for the jump number of interval orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q921022)
