Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 6.5 Algorithms for Interval Orders
Algorithm 6.18 . Poset to Interval Representation.
Input: An interval order \(\mbf{P}=(X,P')\text{.}\)
Determine
\(D(x)\) for each
\(x\in X\text{.}\)
Write down
\(\mc{D}\) as
\(\{\} = D_{1} \subsetneq D_{2}\subsetneq \cdots\subsetneq D_{d}\text{.}\)
Determine
\(U(x)\) for each
\(x\in X\text{.}\)
Write down
\(\mc{U}\) as
\(U_{1} \supsetneq U_{2}\supsetneq \cdots\supsetneq U_{d} = \{\}\text{.}\)
For each
\(x\in X\text{,}\) find
\(D(x) = D_{i}\) and
\(U(x)=U_{j}\text{.}\) Then let
\(I(x)=[i,j]\text{.}\)
(Optional unless instructed) Draw the interval representation.
Peer instruction question 1.
This algorithm has benefits and drawbacks:
Benefit
Uses the smallest number of endpoints possible (because
\(|\mc{D}| = |\mc{U}|\) ).
Drawback
Creates lots of trivial intervals of the form
\([3,3]\text{.}\)
Activity 6.5.1 .
(a) Use the algorithm to determine if the posets on your handout are interval orders (and find an interval representation if they are).
(b) Suppose you learn that the down sets and up sets are totally ordered by inclusion and that there are
\(d\) down sets (and thus
\(d\) up sets). If the poset has a point that is incomparable to every other point, what interval would the algorithm assign?
Greedy or First Fit Algorithms.
The simplest algorithms for many problems are “greedy” in the sense that they look at
in some predetermined order and assign them to something by trying to use as few
as possible at the moment.
There’s usually an order for which a greedy algorithm gives an optimal result, but finding that order is often hard.
First Fit can often succeed if there’s a “natural” order to use.
Algorithm 6.19 . First Fit for Chain Partitioning Interval Orders.
Fix an order in which intervals will be considered.
Assign intervals to chains
\(C_{1},C_{2},\dots\text{.}\)
When considering a new interval, determine which chains it can be added to.
Add it to chain with smallest subscript.
If cannot add to any existing chain, make a new one with subscript as small as possible.
Peer instruction question 2
Algorithm 6.20 . Optimal First Fit for Chain Partitioning Interval Orders.
Consider the intervals in order by left endpoint.
Break ties by choosing interval with smallest label.
Assign intervals to chains
\(C_{1},C_{2},\dots\text{.}\)
When considering a new interval, determine which chains it can be added to.
Add it to chain with smallest subscript.
If cannot add to any existing chain, make a new one with subscript as small as possible.
Peer instruction question 3.
Example 6.21 .
Let’s use First Fit (optimally) to find a chain partition of this interval order and the width of the interval order.
Activity 6.5.2 .
Use First Fit to find the width of the interval orders whose interval representations are on your handout. Also find a partition into as few chains as possible.
