Giovanni Righini
Dipartimento diInformati a
PoloDidatti o edi Ri er a diCrema
Università degli Studi diMilano
Via Bramante65,26013 Crema, Italy
1 Introdu tion
In these notesI presentsomeexamplesof dis reteoptimization problems solvedby dynami programming
(D.P. forshort). Thebasi stepsin thedesignofaD.P.algorithmarethesamein allexamples:
1. Deneasequen eofde isions,that orrespondsto determiningasolution.
2. Denethestate. Thestateistheamountofinformationthat oneneedsto knowwhensomede isions
inthesequen ehavealreadybeentakenandothersarestilltobetaken. Theinformationinthestate
mustbeenoughtodeterminethefeasibilityandthe ostof theremainingde isions.
3. Deneare ursiveextensionfun tion,i.e. howthe ostofstates anbe omputedfromthe ostofother
states.
The exe ution of a D.P. algorithm resembles the sear h for an optimal path on an a y li and weighted
digraph, from agiven sour enode orrespondigto anempty solution(node isiontaken)to agiven target
node orresponding toa ompletesolution (allde isionstaken). Thestru ture and thesize ofthe digraph
depend ontheproblem at hand and theydeterminethe omplexityof theD.P. algorithm. WhentheD.P.
algorithm terminates,thelabel( osttobeminimizedorvaluetobemaximized)ofthenalstategivesthe
optimalvalueoftheobje tivefun tion.
Besides omputingtheoptimalvalue,oneusuallywantstore onstru tafeasiblesolutionwiththatvalue,
i.e. anoptimalsolution. Thisisa hievedbys anningthesequen eofthede isionsba kward,fromthenal
statetotheinitialstate. Forea hstateitsoptimalprede essorissele tedandforthispurposeitisrequired
that theoptimalprede essorhasbeenstoredforea hstate.
For ea h example, I will provide the des ription of the problem, the des ription of one or more D.P.
algorithms, the orrespondinga y li weighteddigraphs,the omplexityofthe algorithm. Ea hproblem is
illustrated by anumeri alexample with itssolution. I also providethe pseudo- ode of theD.P. algorithm
allowingforane ientandstraightforwardimplementation.
Renementssu hasbi-dire tionalD.P.andtheuseofsuitabledata-stru tureswillbealsodis ussed.
The problem. Given an a y li digraph
D = (N , A)
with|N | = n
and|A| = m
and a ost fun tionw : A 7→ ℜ
,nd theshortestpathfrom agivennodes ∈ N
to agivennodet ∈ N
. Adigraph isa y li ifandonlyifitdoesnot ontainany ir uit.
Step1: sequen ing thede isions. Sin e
D
isa y li ,itispossibletosortitsnodesintopologi alorder inO(m)
. IfD
isalsolayered,itispossibletosortthelayersanditisnotne essarytosortthenodesinea hlayer(anyorder ts). Weindi ateby
P red(j) ⊂ N
theset ofprede essorsofea hnodej ∈ N
:P red(j) = {i ∈ N : (i, j) ∈ A}.
Step 2: deningthe state. Thestate onsists ofthelastrea hednode. All pathsfromnode
s
to nodei ∈ N
orrespondto sub-poli iesleadingto thesamestate. Hen e states havethefollowing (trivial)form:{i}
,withi ∈ N
. The ostasso iatedwithea h state{i}
isindi atedbyc(i)
.Step 3: state extension.
•
Initialization:c(s) := 0
.•
Extension:c(j) := min i∈P red(j) {c(i) + w ij }
.Theoptimalvalueis
c(t)
whenthealgorithmstops.Complexity. Thea y li weightedstate-transition digraphof theD.P. algorithm isthedigraph
D
itself.Thisis whythisexampleissuitbaleto bepresentedastheintrodu toryproblemtoillustrateD.P..
Thetime omplexityimmediately follows: when extendingstates, ea h ar ofthedigraph is onsidered
onlyon e;hen ethe omplexityis
O(m)
.Sin eea h nodehasasinglelabel
c(i)
anditsvalueis omputedonlyon e,theresultingD.P. algorithmisalabelsettingalgorithm.
Pseudo- ode. Thepseudo- odeoftheD.P. algorithmis shownin Algorithm2.1. Ave tor
π
re ordstheoptimalprede essorstateforea hstate,i.e. theoptimalprede essornodeforea hnodeinthis example.
Thesub-routine
ComputeP redecessors
isneededwhenthedigraphisgivenininputasalistofweightedar s. Insu ha asethelist issequentiallys annedandforea har
(i, j) ∈ A
nodei
isinsertedinP red(j)
.The omputational omplexityofthisoperationisobviously
O(m)
.The omputational omplexityofthelabelextensionis
O(m)
, asalreadyproven.The omputational omplexityof the lastpart, where anoptimal solutionis produ ed, depends onthe
requiredoutputformat: ifabinaryve tor
x
isrequired,thenthe omplexityisO(m)
,asshowninAlgorithm2.1, be ause
m
binary variables mustbe assigned avalue; if asetX
of sele tedar s is required, then theomplexityis
O(n)
, be ausetheinitializationX ← ∅
takes onstanttime andno morethann − 1
ar s anbelongtothe
s − t
path.1:
T opologicalSort
;⊲ O(m)
2:
ComputeP redecessors
;⊲ O(m)
3: /*Negle tunrea hablenodes(nodesbefore
s
),ifany*/4: for
j = 0, . . . , s − 1
do⊲ O(n)
5:
c(j) ← ∞
;6: /*Initialization*/
7:
c(s) ← 0
;8: /*Extension*/
9: for
j = s + 1, . . . , t
do10: for
i ∈ P red(j)
do11: if
(c(i) + w ij < c(j))
then12:
c(j) ← c(i) + w ij
;13:
π(j) ← i
;14: /*Optimalobje tivefun tion value*/
15:
z ∗ ← c(t)
;16: /*Retrievalofanoptimalsolution*/
17: for
(i, j) ∈ A
do⊲ O(m)
18:
x ∗ (i, j) ← 0
;19:
j ← t
;20: while
(j > s)
do⊲ O(n)
21:
x ∗ (π(j), j) := 1
;22:
j ← π(j)
;return
z ∗ , x ∗
Label orre ting variation. A variationoftheD.P. algorithmis obtainedbyextendingthelabelsfrom
ea hstatetoitssu essors. Let
Succ(i)
bethesetofallsu essorsofnodei
,i.e.Succ(i) = {j ∈ N : (i, j) ∈ A}.
ThelabelextensionpartofAlgorithm2.1 ouldberepla edbythefollowingAlgorithm2.2.
Algorithm2.2Labelextension
9: for
i = s, . . . , t − 1
do10: for
j ∈ Succ(i)
do11: if
(c(i) + w ij < c(j))
then12:
c(j) ← c(i) + w ij
;13:
π(j) ← i
;Thetime omplexityisthesame,i.e.
O(m)
, be auseeveryar isexaminedon e. However,inthis asethelabelofea hstate anbeupdatedseveraltimes. Thereforethisvariationisalabel orre tingalgorithm.
requires to omputeashortestpathfrom node
s = 0
tonodet = 9
.0
1
2
3
4
5
6
7
8
9 6
8
13
9
15 8
10
12 8
7
15
20
8
7
3
4
Figure1: A weighteda y li (andlayered)digraph.
Figure2showstheiterationin whi h node5is labeled. Nodes0to 4havealreadybeenlabeled. Their
asso iated ostsareshownbytheblue labelsinFigure2. Optimalprede essorsarerepresentedbyredar s.
Node 5is nowlabeled by omparing three prede essorstates, yielding osts equalto 21 (from node1), 18
(fromnode2)and21(fromnode3)andsele tingthebest option(the se ondone).
0 0
1 6
2 8
3 13
4 15
5 18
6
7
8
9 6
8
13
9
15 8
10
12 8
7
15
20
8
7
3
4
Figure2: Astateextension.
stru ted byfollowingthe hainofprede essors
π
ba kwardfrom node9tonode1: theresultisrepresented bythethi kredar s.0 0
1 6
2 8
3 13
4 15
5 18
6 20
7 30
8 26
9 30 6
8
13
9
15 8
10
12 8
7
15
20
8
7
3
4
Figure3: Theexamplesolved.
The problem. Givenadigraph
D = (N , A)
with|N | = n
and|A| = m
and a ostfun tionw : A 7→ ℜ
,ndtheshortestpathfromagivennode
s ∈ N
toagivennodet ∈ N
. Thedigraphisnot onstrainedtobe a y li asinthepreviousexample;we onsidernowageneri digraph,possibly ontaining ir uits. Howeverir uitsareguaranteednottohavenegative ost.
Step1: sequen ingthede isions. Theproblemisverysimilartothepreviousone,butnowthedigraph
is nota y li andthereforeitsnodes annotbesortedasin thepreviousexample. We anreformulate the
problem onana y li andlayereddigraph
D ′ = (N ′ , A ′ )
, where• N ′
ismadebyasetL
ofn
layers;•
ea hlayerL k
ontainsa opyofea h nodeinN
;hen eea hnodeinN ′
isindi atedbyapair(i, k)
;•
forea har(i, j) ∈ A
thereisanar from node(i, k)
tonode(j, k + 1)
forea hlayerk = 1, . . . , n − 1
.Weindi ateby
P red ′ (j, k) ⊆ N ′
thesetofprede essorsofea hnode(j, k) ∈ N ′
:P red ′ (j, k) = {(i, k − 1) ∈ N ′ : (i, j) ∈ A ′ } ∀k = 2, . . . , n.
Theprede essorsofea hnodeinlayer
k
belongto layerk − 1
. Thenodesin layer1
havenoprede essor.The
n
layersofdigraphD ′
representthen
stagesofthe D.P. algorithm. Atea h stagek
the algorithmomputesand omparespathsmade by
k − 1
ar s. Sin enofeasible solution an ontainmorethann − 1
ar s,
n
layersaresu ienttoimpli itlyenumerateallpossiblesolutions.Afterthis reformulation,the shortestproblem on ageneri digraph with
n
nodes is translatedinto theshortestpathproblemonana y li digraphwith
m(n − 1)
nodes. Therefore,thesameD.P.algorithmshownin thepreviousexampleapplies.
Step2: deningthestate. Thestate onsistsofthelastrea hednodein
N ′
. Alls − i
pathsmadebyk
ar s orrespondto sub-poli iesleadingto thesamestate. Hen e labelshavethefollowingform:
{i, k}
,withi ∈ N
andk = 1, . . . , n
. The ostasso iatedwithea hlabel{i, k}
isindi atedbyc(i, k)
.Step 3: labelextension.
•
Initialization:c(s, 1) = 0 c(i, 1) = ∞ ∀i 6= s
.•
Extension:c(j, k) = min (i,k−1)∈P red ′ (j,k) {c(i, k − 1) + w ij , c(j, k − 1)}
.Theoptimalvalueis
c(t, n)
.Remark1. Thealgorithm anpossiblyterminateevenbeforerea hingstage
n
: ifno hangeinlabelsisobservedata ertainstage,no hange ano urintheremainingstageseither.
Remark2. Thealgorithm omputestheshortestpathfrom
s
toall theothernodesinN
.Complexity. Whenextendinglabels,ea h ar in
A ′
is onsideredonlyon e. Thenumberofar sinA ′
ism(n − 1)
. Hen ethe omplexityisO(mn)
.Thealgorithm isknownasBellman-Fordalgorithm.
Thelabelofasamenode anbeupdatedseveraltimes(on eforea hstage). ForthisreasontheBellman-
Fordalgorithm isalabel orre tingalgorithm.
A numeri alexample. Figure4showsaweighteddigraph ontaining ir uits. Wewantto omputethe
shortestpathfromnode1tonode6.
1
2
3
4
5
6 20
10 63
72
0
70
5
40
34
100
-20
-5
36
-31
5
80
Figure4: Aweighteddigraph.
1,1
2,2
3,2
4,2
5,2
6,2
2,3
3,3
4,3
5,3
6,3
2,4
3,4
4,4
5,4
6,4
2,5
3,5
4,5
5,5
6,5 0
20
10
63
72
∞
15
10
50
44
90
13
10
49
44
85
13
10
49
44
83 20
10
63
72
0
40
70
5
40
34
100 -20
-5
36 -31
5
80
0
40
70
5
40
34
100 -20
-5
36 -31
5
80
0
40
70
5
40
34
100 -20
-5
36 -31
5
80
Figure5: Thestate-transitiongraphandthestateextensions. Costsarerepresentedinblue;optimalprede-
essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.
The problem. Givenadigraph
D = (N , A)
with|N | = n
and|A| = m
and a ostfun tionw : A 7→ ℜ
,ndtheshortestHamiltonianpathfrom agivennode
s ∈ N
toagivennodet ∈ N
.A Hamiltonianpathisapaththatvisitsallnodesofthedigraphon e. Notethatw.l.o.g. we anassume
A
to be omplete;just onsidermissingar sasar swithaverylarge ost.
Step 1: sequen ing the de isions. Similarlyto theprevious example,sin e
D
is nota y li , itis notpossibletosort itsnodesandto settheirlabelspermanently. Weresortto anauxiliarya y li and layered
digraph
D ′
usingthesame onstru tionofthepreviousexample.Step 2: deningthe state. Thestatedoesnot onsistonlyof thelastrea hednode. Inorderto he k
the feasibility ofthe solutionone must knowwhi h nodes havealready beenvisited. All pathsfrom node
(s, 1)
to node(i, k) ∈ N ′
orrespond to sub-poli ies leadingto thesamestate ifand only iftheyalso visitthe same subsetof nodes. Hen e labelshavethe following form:
{i, k, S}
, withi ∈ N
andS ⊆ N
. Notethat
k = |S|
,be auseoneadditionalnodeisvisitedeverytimeapathisextended. Thereforetheinformation givenby thelayerindexk
is redundant and anbeomitted. The ost asso iated with ea h label{i, S}
isindi atedby
c(i, S)
.Step 3: labelextension.
•
Initialization:c(s, {s}) = 0
.•
Extension:c(j, S) = min i∈S {c(i, S\{j}) + w ij }
.Theoptimalvalueis
c(t, N )
.Complexity. Thenumberofstatestobelabeledisexponentialin
n
. Thenumberofdistin tvaluesofthepossiblesubsets
S
is2 n
andea hsubsetwithk
nodesappearsink
dierentstates(dependingonwhi histhelastvisitednode). Hen ethenumberofstatesis
O(n2 n )
. Whenextendinglabelsthenumberofprede essors forea hstateisO(n)
. Hen ethe omplexityoftheD.P.algorithmisO(n 2 2 n )
.Dominan e. Dominan e onsistsofdeletingsomestatesfromfurther onsiderationbe ausethereisaguar-
anteethat theydonot orrespondto optimalsub-poli iesandthereforethe orrespondingpartialsolutions
annot bepartof optimal solutions. Inthese examplesthe dominan e riteriaare impli itly applied when
thelabelobtainedfromthebestprede essorissele tedandallotherextensions(i.e. thelabelsprodu edby
the other prede essors)are dis arded. This is aspe ial ase of dominan e: astatedominates anotherone
whenithasasmaller ostandallinformationisidenti alinbothstates(samelastvisitednode,samelayer,
samesubsetofvisitednodes,...).
1
2
3
4
5
6 20
10 63
72
0
40
70
5
40
34
100
-20
-5
36
-31
5
80
Figure6: Aweighteddigraph. Wewanttondtheminimum ostHamiltonianpathfromnode1tonode6.
Notethat thedigraph ontainsar swithnegative ost. Howeveritdoesnot ontain ir uitsofnegative
ost. Cir uitsofzero ostareallowedandindeed thereisone, ontainingnodes4and5. Alsonotethatnot
all ar s are present. This makesthe instan e easierto solveand the orrespondingstate-transition graph
easiertorepresent: somestateshaveauniqueprede essor(seeFigure7).
Theoptimalsolutionisthepath
(1, 3, 4, 5, 2, 6)
,whose ostis84. Dominan e anbeobservedontherightpartof Figure 7,where somestateshavemorethan oneprede essor: this meansthat they anberea hed
in dierentways. Forinstan e, state
{5, 1345}
anberea hedthroughthesequen es(1, 4, 3, 5)
with ost77and
(1, 3, 4, 5)
with ost45. Theformersub-poli yisdominatedbythelatterone. Owingtodominan e,thestatesgeneratedbytheD.P.algorithmarefewerthanallpossiblesequen es(sub-poli ies).
1,{1}
2,{1,2}
3,{1,3}
4,{1,4}
5,{1,5}
2,{1,2,3}
2,{1,2,5}
3,{1,2,3}
3,{1,3,4}
4,{1,2,4}
4,{1,3,4}
4,{1,4,5}
5,{1,3,5}
5,{1,4,5}
2,{1,2,3,4}
2,{1,2,3,5}
2,{1,2,4,5}
3,{1,2,3,4}
3,{1,2,3,5}
3,{1,3,4,5}
4,{1,2,3,4}
4,{1,2,4,5}
4,{1,3,4,5}
5,{1,2,3,5}
5,{1,2,4,5}
5,{1,3,4,5}
2,{1,2,3,4,5}
3,{1,2,3,4,5}
4,{1,2,3,4,5}
5,{1,2,3,4,5}
6,{1,2,3,4,5,6}
0
20
10
63
72
41
20
43
60
50
77
44
58
13
27
40
41
57
55
81
49
54
55
45
14
27
53
50
84 20
10
63
72
0
40
5
40
34
-20
-5
-31
5
40
0
40
40
34 5
34 -20
-5
-5
-20
-31
5
-31
40 0
34 40 5
-5 5 -20 -31
70
100
36
80
Figure7: Thestate-transitiongraphandthestateextensions. Costsarerepresentedinblue;optimalprede-
essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.
The problem. Giventwostrings
S 1
andS 2
, i.e. twosequen esof hara terstakenfromagivenalphabetA
,givenanadditional hara terX noto urringinS 1
andS 2
andgivena ostfun tionw : A + × A + 7→ ℜ
,where
A + = A ∪ {“X ′′ }
,ndtheminimum ostalignment.Analignmentisgivenbyinsertinganynumberof hara tersX inanypositionsalongthetwosequen es,
sothat thenal sequen es havethesamelength. The ost ofan alignmentis thesum ofthevaluesof the
ost fun tion omputedfor allpositionsalong theresultingsequen es: ea h pairof hara ters o urringin
thesamepositionistheargumentofthefun tionforthat position.
Formally,let
S 1 +
andS 2 +
bethetwosequen esaftertheinsertionoftheo urren esoftheX hara ter.Let
L
be their length. Let indi ate byS i + (k)
the hara ter in positionk
in sequen eS i +
. The ostof thealignmentis
P L
k=1 w(S 1 + (k), S 2 + (k))
.Remark. Obviouslythe fun tion
w
is dened to penalize misalignments,i.e. thepresen e of dierent hara tersin the sameposition,and to rewardalignments, i.e. thepresen e of identi al hara ters in thesamepositions. The alignmentof a hara terin
A
witha hara terX is usuallypenalized,but lessthana misalignment. Aligning two hara ters X is never optimal: they anbe deleted from both sequen es,
yieldingabettersolution.
Step1: sequen ing the de isions. Inthisexamplewe onsidertwosequen esofde isions,oneforea h
string. Forea hpositiononehastode idewhethertoinserta hara terX ornotinthestring.
Step 2: dening the state. The state must represent whi h de isionshave already been taken: sin e
there aretwosequen es, thestate ontainstwoindi es, say
k 1
andk 2
, indi atinghowmanypositionshavealreadybeens annedandalignedinea hsequen e. Nofurtherinformationisrequiredto he kthefeasibility
oftheremainingde isions. Hen ethestateshavethefollowingform:
{k 1 , k 2 }
. The ostasso iatedwithea hstate
{k 1 , k 2 }
isindi atedbyc(k 1 , k 2 )
.Step 3: labelextension.
•
Initialization:c(0, 0) = 0
.•
Extension:c(k 1 , k 2 ) = min{c(k 1 − 1, k 2 ) + w S 1 (k 1 ),“X ′′ , c(k 1 , k 2 − 1) + w “X ′′ ,S 2 (k 2 ) , c(k 1 − 1, k 2 − 1) + w S 1 (k 1 ),S 2 (k 2 ) }
.Theoptimalvalueis
c(n 1 , n 2 )
,wheren 1
andn 2
arethelengthsofthegivensequen es.Complexity. Thenumberofstatestobelabeledis
(n 1 + 1)(n 2 + 1)
. Whenextendinglabelsthenumberofprede essorsforea hstateisatmostequaltothree. Hen ethe omplexityoftheD.P.algorithmisquadrati
in theinputsize.
Instan e
S1
: AA ABABS2
: BABA BBCost A B X
A 0 2 1
B 2 0 1
X 1 1 -
Solution 1:
S 1
=A AABA BS 2
=BABABBCost=8
Solution 2:
S 1
=AAA BABXXS 2
=BAXXBABBCost=4
Figure8: Asampleinstan eofthestringmat hing problemwithtwofeasiblesolutions.
0,0 0,1 0,2 0,3 0,4 0,5 0,6
1,0 1,1 1,2 1,3 1,4 1,5 1,6
2,0 2,1 2,2 2,3 2,4 2,5 2,6
3,0 3,1 3,2 3,3 3,4 3,5 3,6
4,0 4,1 4,2 4,3 4,4 4,5 4,6
5,0 5,1 5,2 5,3 5,4 5,5 5,6
6,0 6,1 6,2 6,3 6,4 6,5 6,6
2 3 4 5 6
1 2 1 2
3 4 5
2 3 2 3 2
3 4
3 4
3
4
3
4 5
4 3 4
3
4
3
4
5 4 3 4
3 4
5
6 5 4 3 4
3 4
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2 0 2 0 2 2
2 0 2 0 2 2
2 0 2 0 2 2
0 2 0 2 0 0
2 0 2 0 2 2
0 2 0 2 0 0
Figure 9: Thestate-transition graph. Thegraphisdire ted,a y li andlayered: ea h node anberea hed
fromatmostthreeprede essorsintheprevioustwolayers.Costsasso iatedwiththestatesarerepresentedin
blue. Optimalprede essorsarerepresentedbyredar s. Optimalsolutionsareindi atedbyboldednumbers
andthi kar s. Forthissmallinstan e multipleoptimalsolutionsexist.
6
p
-medians on a lineThe problem. Givenastraightlineandaset
N = {1, . . . , n}
ofpointsalongitinxedpositionsx(i) ∀i ∈ N
,ndtheoptimalpositionalongthelineforp
additionalpoints, alledmedians,su hthatthesumofthedistan esbetweenea hpointin
N
andits losestmedian isminimized. W.l.o.g. weassumethat thepointsin
N
areorderedin thesameorderastheyo uralongtheline.Remark1. The
p
-medianproblemisNP-hard ongraphs,butthissimpliedversioninwhi hallpointslieonastraightlineispolynomiallysolvablebydynami programming.
Remark2. The
1
-medianproblemonalineiseasy(itiseasy,i.e. polynomiallysolvable,evenongeneral graphs). Ifthenumberofpointsisodd,theoptimallo ationofthemedian oin ideswiththe entralpoint;ifthe numberof pointsiseven, theoptimallo ationof themedianis anywhere alongthesegmentbetween
the two entral points. We indi ate by
w(i, j)
theoptimal (minimum) ostof lo ating a singlemedian toservethepointsin theinterval
[i, j]
,withi ∈ N, j ∈ N, j ≥ i
.Step 1: sequen ing the de isions. Allsolutionsindu e apartition of
N
intonon-overlappingintervalsalongthelineandwede idehowmanymediansareusedtoservethepointsen ountered.
Step2: deningthe state. Thestaterepresentswhi hde isionshavealreadybeentaken: atea hstage
inthede isionpro essweneedtoknowwhi histhelasts annedpoint
i ∈ N
andthenumberm
ofmediansuseduptothatpoint. Hen ethestateshavethefollowingform:
{i, m}
. The ostasso iatedwithea hstate{i, m}
isindi atedbyc(i, m)
: itindi ates theminimum osttoservethepointsin[1..i]
withm
medians.Step 3: labelextension.
•
Initialization:c(i, 1) = w(1, i) ∀i ∈ N
.•
Extension:c(i, m) = min j<i {c(j, m − 1) + w(j + 1, i)} ∀i ∈ N : i ≥ 2 ∀m : 2 ≤ m ≤ min{i, p}
.Theoptimalvalueis
c(n, p)
.Complexity. Thenumberof statesto belabeledis givenby
np
and sin ep ≤ n
itis notlargerthann 2
.Whenextendinglabels,thenumberofprede essorsforea hstateis
O(n)
. Hen e the omplexityoftheD.P.algorithmis
O(n 2 p)
orO(n 3 )
.A numeri alexample. Figure10representsaninstan eofthe
p
-median problemonaline.0
❜
A
2
❜
B
4
❜
C
7
❜
D
10
❜
E
11
❜
F
14
❜
G
18
❜
H
19 20
Figure 10: Aninstan e ofthe
p
-median problemonaline. Forbetterreadabilitytheindi es1, . . . , n
ofthegivenpointshavebeenrepla edbyletters. Inthisinstan e
p = 3
.The osts
w(j, i)
for all pairs of points an be omputed inO(n 2 )
exploiting the property outlined inRemark 1bythefollowingsimplealgorithm.
Algorithm6.1
1: for
j = 1, . . . , n − 1
do2:
opt := j
;3:
i := j
;4:
w(j, i) := 0
;5:
paritybit := 1
;6: while
i < n
do7:
i := i + 1
;8:
paritybit := 1 − paritybit
;9:
w(j, i) := w(j, i − 1) + (x(i) − x(opt))
;10: if (
paritybit = 0
)then11:
opt := opt + 1
;Theresulting ostmatrixisasfollows.
w A B C D E F G H
A 0 2 5 11 15 22 30 39
B 0 3 6 10 14 22 30
C 0 3 4 8 15 23
D 0 1 4 11 16
E 0 3 7 12
F 0 4 5
G 0 1
H 0
The orrespondingstates-transitionsgraph,withtheoptimalsolution,isrepresentedin Figure11.
A,1
B,1
C,1
D,1
E,1
F,1
B,2
C,2
D,2
E,2
F,2
G,2
H,3 2
5
11
15
22
0
2
5
6
9
16
14 0
3
6
10
14
22 0
3
4
8 15
0
1 4
11
0
3 7
0
4
0
30
23
16
12
5
1
Figure 11: Thestates-transitionsgraphandthestatesextensions. Costsofthestatesare indi atedin blue;
ostsofthetransitionsareindi atedinred. Theoptimalsolutionisindi atedbybolded ostsandthi kar s.
7 The binary knapsa k problem
The problem. Givenaset
N = {1, . . . , n}
ofitemswithavaluev i ∀i ∈ N
andaweightw i ∀i ∈ N
,sele tthe subsetof itemsof maximumvaluesu hthat the overall weightof thesele teditemsdoesnotex eeda
given apa ity
W
.Step1: sequen ingthede isions. We an onsidertheitemsa ordingtotheirnumberingfrom1to
n
.Forea hitemwehavetode idewhethertosele titornot. Hen ewehaveasequen eof
n
binaryde isions.Step2: deningthestate. Atea hpointalongthede isionpro essweneedtoknowtheresidual apa ity
i v i w i
1 45 4
2 55 5
3 42 4
4 62 6
5 61 6
6 80 8
7 69 7
Table1: Asmallinstan e. Itemsaresorteda ordingto theire ien y
v i /w i
. The apa ityisW = 16
.0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 0 0 0 45 45 45 45 45 45 45 45 45 45 45 45 45
2 0 0 0 0 45 55 55 55 55 100 100 100 100 100 100 100 100
3 0 0 0 0 45 55 55 55 87 100 100 100 100 142 142 142 142
4 0 0 0 0 45 55 62 62 87 100 107 117 117 142 149 162 162
5 0 0 0 0 45 55 62 62 87 100 107 117 123 142 149 162 168
6 0 0 0 0 45 55 62 62 87 100 107 117 125 142 149 162 168
7 0 0 0 0 45 55 62 69 87 100 107 117 125 142 149 162 169
Table2: Theoptimalsolution(in bold):
z ∗ = 169
,x ∗ = [1, 1, 0, 0, 0, 0, 1]
.the stateshavethefollowingform:
{i, q}
, wherei
indi ates the last item onsidered in thesequen e andq
indi ates the apa ityused. The valueasso iated withea h state
{i, q}
isindi ated byz(i, q)
: itindi atesthemaximumvaluethat anbea hieved withtherst
i
items,using anamountof apa ityequaltoq
. Adummy initialstate indi atesthat at thebeginningno itemhasbeen onsidered and no apa ityhasbeen
used.
Step 3: labelextension.
•
Initialization:z(0, q) = 0 ∀q = 0, . . . , W
.•
Extension:z(i, q) =
z(i − 1, q) ∀i ∈ N ∀q < w i
max{z(i − 1, q), z(i − 1, q − w i ) + v i } ∀i ∈ N ∀q = w i , . . . , W.
Theoptimalvalueis
max q=0,...,W {z(n, q)}
.Complexity. Index
i
rangesintheinterval[0 . . . , n]
;thenumberofpossiblevaluesfori
isn + 1
. Indexq
rangesin the interval
[0 . . . , W ]
; thenumberof possiblevaluesforq
isW + 1
. Hen ethe numberofstatesgrowsas
O(nW )
. Whenextendinglabels,thenumberofprede essorsforea hstateis2
. Hen etheworst- asetime omplexity ofthe D.P. algorithm is
O(nW )
. This omplexityis notpolynomial, be auseW
doesnotdeterminethesizeoftheinstan e,like
n
;ratheritisthevalueofadatumoftheinstan e. Inthis ase,wesaythatthe omputational omplexityispseudo-polynomial. Dynami Programmingisaverypowerfulte hnique
to designpseudo-polynomial omplexityalgorithms for
N P
-hardproblems. IfanN P
-hardproblem admitssu hanalgorithm,itis lassiedas weakly
N P
-hard.Anumeri alexample. Table1showsasmallinstan eofthebinaryknapsa kproblem. The orresponding
optimalsolutionisreportedinTable7.
Implementation. Abasi versionoftheD.P.algorithmdes ribedabovedire tly omesfromthedenition
oftheextensionfun tion. It onsistsofllingthematrixshowninFigure7rowafterrow.
Howeverinthisalgorithmmanyiterationsarewasted,be ausenoallentriesofthematrix
z
areneeded. A2: /*Inizialize*/
3: for
q = 0, . . . , W
do4:
z[0, q] := 0
;5: /*Computeallstates*/
6: for
i = 1, . . . , n
do7: for
q = 0, . . . , w i − 1
do8:
z[i, q] := z[i − 1, q]
;9:
f lag[i, q] := 0
;10: for
q = w i , . . . , W
do11: if (
z[i − 1, q − w i ] + v i > z[i − 1, q]
)then12:
z[i, q] := z[i − 1, q − w i ] + v i
;13:
f lag[i, q] := 1
;14: else
15:
z[i, q] := z[i − 1, q]
;16:
f lag[i, q] := 0
;17: /*Find theoptimalvalue*/
18:
z ∗ := 0
;19: for
q = 0, . . . , W
do20: if
(z[n, q] > z ∗ )
then21:
z ∗ := z[n, q]
;22:
q ∗ := q
;23: /*Re onstru ttheoptimalsolution*/
24: for
i = n, . . . , 1
do25:
x ∗ [i] := f lag[i, q ∗ ]
;26: if
(f lag[i, q ∗ ] = 1)
then27:
q ∗ := q ∗ − w i
;return
z ∗
,x ∗
asalinkedlist. Thealgorithm startsfrom asinglestate ofnullvalueon row
0
and onlyexisting statesinrow
i
generate su essorstates in rowi + 1
. Everytime astate(i, q)
is generated, itis ne essaryto he kwhetheranotherstatealreadyexistswiththesamevalueof
q
. Ifitexists,thena omparisonisneededwhi hof thetwostatesdominate. Thesear hforthis staterequires ingeneralmorestepsthanadire t a essto
amatrix entry. Howeverthis an be ompensated bythesparsityof thedata-stru ture: ea hlinked list is
likelyto ontainlessstatesthanasinglerowofthematrix
z
,espe iallyintheearliestiterations.The notation used in 7.1 is the following. Ea h row is a doubly linked list made of re ords with the
followingelds:
• capac
: thevalueoftheused apa ity(q
);• value
: thea umulatedvalue(z
);• lef t
andright
: pointerstotheadja entre ords;• pred
: pointerto theoptimalprede essorstate;• item
: lastelementinsertedintotheknapsa k.An array
tail
ontainsthepointerstotherightmost elementsofea hrow.Algorithm7.1Knapsa k(dynami data-stru ture)
1:
Initialize
;2: /*Computeallstates*/
3: for
i = 1, . . . , n
do4:
CopyList(i)
;5: /*Initializepointersto s anthelist*/
6:
p := tail[i]
;7:
s := tail[i]
;8: repeat
9: if
(pˆ.capac + w i ≤ W )
then10: while
(sˆ.capac > pˆ.capac + w i )
do11:
s := sˆ.lef t
;12: if
(pˆ.capac + w i > sˆ.capac)
then13:
CreateN ewState(p, s, i)
;14: else
15: /*Dominan etest*/
16: if
(sˆ.value < pˆ.value + v i )
then17:
sˆ.value := pˆ.value + v i
;18:
sˆ.item := i
;19:
sˆ.pred := p
;20:
p := pˆ.lef t
;21: until
(p = nil)
;22:
RetrieveOptimalSolution
;Algorithm7.2
Initialize
1:
N ew(tail[0])
;2:
tail[0]ˆ.value := 0
;3:
tail[0]ˆ.capac := 0
;4:
tail[0]ˆ.lef t := nil
;5:
tail[0]ˆ.right := nil
;6:
tail[0]ˆ.pred := nil
;Algorithm7.3
CopyList(i)
1:
p := tail[i − 1]
;2:
tail[i] := nil
;3: while
(p <> nil)
do4: if
(tail[i] = nil)
then5:
N ew(tail[i])
;6:
s := tail[i]
;7:
sˆ.capac := pˆ.capac
;8:
sˆ.value := pˆ.value
;9:
sˆ.item := pˆ.item
;10:
sˆ.right := nil
;11:
sˆ.lef t := nil
;12:
sˆ.pred := tail[i − 1]
;13: else
14:
N ew(sˆ.lef t)
;15:
sˆ.lef tˆ.capac := pˆ.capac
;16:
sˆ.lef tˆ.value := pˆ.value
;17:
sˆ.lef tˆ.item := pˆ.item
;18:
sˆ.lef tˆ.right := s
;19:
sˆ.lef tˆ.lef t := nil
;20:
sˆ.lef tˆ.pred := p
;21:
s := sˆ.lef t
;22:
p := pˆ.lef t
;Algorithm7.4
CreateN ew(p, s, i)
1:
N ew(t)
;2:
tˆ.lef t := s
;3:
tˆ.right := sˆ.right
;4:
sˆ.right := t
;5: if
(tail[i] = s)
then6:
tail[i] := t
7: else
8:
tˆ.rightˆ.lef t := t
;9:
tˆ.capac := pˆ.capac + w i
;10:
tˆ.value := pˆ.value + v i
;11:
tˆ.item := i
;12:
tˆ.pred := p
;Algorithm7.5
RetrieveOptimalSolution
1:
z ∗ := 0
;2: for
i = 1, . . . , n
do3:
x[i] := 0
;4:
p := tail[n]
;5: while
(p <> nil)
do6: if
(pˆ.value > z ∗ )
then7:
z ∗ := pˆ.value
;8:
p ∗ := p
;9:
p := pˆ.lef t
;10: while
(p ∗ ˆ.pred <> nil)
do11:
x[p ∗ ˆ.item] := 1
;12:
p ∗ := p ∗ ˆ.pred
;z ∗ x ∗
1 0 45
2 0 45 55 100
3 0 45 55 87 100 142
4 0 45 55 62 87 100 107 117 142 149 162
5 0 45 55 62 87 100 107 117 123 142 149 162 168
6 0 45 55 62 87 100 107 117 125 142 149 162 168
7 0 45 55 62 69 87 100 107 117 125 142 149 162 169
Table 3: The sparse matrix in the implementation using dynami data-stru tures: about one half of the
statesarenotevaluated.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 45
2 0 45 55 100
3 0 45 55 87 100 142
4 0 62 69 80 123 131 142 149
5 0 61 69 80 130 141 149
6 0 69 80 149
7 0 69
Table4: Thetwosparsesub-matri esin thebi-dire tionalimplementation: about
75%
ofthestatesarenotgenerated.
Inthisimplementationalargepartofthe matrix(i.e. alargepartof thestatespa e)isnotgenerated,
asshowninTable??.
However, onsideringhowmanyelementaryoperationsareneededinthese ondimplementation ompared
totherstone,thissavingmaybeinsu ienttojustifytheuseofdynami data-stru turestosolvethistoy
instan e. Theadvantageofthese ondimplementationislikelytobemeaningfulonlyforverylargeinstan es
(where omputingtimeisalsomoresigni ant).
An observation dire tly stemming from the analysis of Table ?? is that the number of states grows
with index
i
: top rowsin the matrixare sparserthan bottom rows. This suggestsafurther improvement:bi-dire tionalD.P.. Inbi-dire tional D.P. non-dominated statesaregenerated in bothdire tions along the
sequen eofde isions;thereforewehavetomanageforwardandba kwardstatesseparatelyandindependently.
Theextensionofstatesstopswhenasuitablehalf-waypoint isrea hed. Thedenitionofthisstop riterion
mustsatisfyafundamentalproperty: itmustbepossibletoobtainanyfeasiblesolutionbysuitably ombining
aforwardstateandaba kwardstate,i.e. twonon-dominatedsub-poli ies. Inourexample,apossible riterion
istheuseoftheitems: forinstan e,wedeneforwardstatesasnon-dominated ombinationsofitems
1 . . . , 3
and ba kward states as non-dominated ombinations of items
4 . . . , 7
. Using the same extension rules offorwardstatesfor generatingba kwardstates,withtheonly dieren ethat itemsare onsidered in reverse
order,weobtaintheresultshowninTable7.
Bi-dire tionalD.P. allowsto de reasesigni antlythenumberof statesto be onsidered. Onthe other
side, itrequires apost-pro essingoperationtojoin pairsofforwardand ba kwardstatesinorder toobtain
solutions. Pairsofstatesmustsatisfythe apa ity onstraint: ea hforwardstatewith apa ity onsumption
q
anbejoined with anyba kwardstatewith apa ity onsumptionnot largerthanW − q
. Thejoin stepanbedonein
O(n)
, asillustratedinTable??.Inthejoinstepea hforwardstateismat hedwiththemost onvenientba kwardstate,thatiswiththe
ba kwardstatewith maximum onsumption among thosesatisfying the apa ity onstraint. Forinstan e,
forwardstate with
q = 5
andz = 55
an be feasibly mat hed with allba kwardstates with onsumption between0
and11
: themost onvenientoneistheba kwardstatewithq = 8
andz = 80
. This anbedonein
O(n)
asshowninAlgorithm7.6: thepseudo- odeassumesanimplementationwithtwolinkedlists,whosetail f w tail bw head f w head bw
FW 0 (0) (0) (0) 45 55 (55) (55) 87 100 (100) (100) (100) 142 (142) (142) (142)
BW 149 142 131 123 (80) (80) (80) 80 69 62 (0) (0) (0) (0) (0) 0
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
149 149 142 131 168 135 135 135 167 169 162 100 100 142 142 142 162
Table5: Thejoinsteprequiresto s antheforwardand ba kwardlistofnon-dominatedstates.
theleftside. Itreturnstheoptimalvalue
z ∗
andtwopointersp ∗
andq ∗
totheoptimalforwardandba kwardstatepair. Sin ethetwolistsares annedonlyon e,theworst- asetime omplexityofthejoinpro edureis
O(n)
.Algorithm7.6
Join
1:
z ∗ := 0
;2:
p := tail f w
;3:
q := head bw
;4: while
(p 6= nil)
and(q 6= nil)
do5: repeat
6: if
(pˆ.value + qˆ.value > z ∗ )
then7:
z ∗ := pˆ.value + qˆ.value
;8:
p ∗ := p
;9:
q ∗ := q
;10:
q := qˆ.right
;11: until
(q = nil)
or(pˆ.capac + qˆ.capac > W )
12: repeat
13:
p := pˆ.lef t
;14: until
(p = nil)
or(pˆ.capac + qˆ.capac ≤ W )
return
z ∗
,p ∗
,q ∗
The problem. Weare givenadis rete-time dynami system, i.e. a system hara terizedby aninput, a
stateandanoutput. Inthisexampletheyareallverysimple,just onsistingofas alarvalue. Inadis rete
set of
T
pointsin timet = 1, . . . , T
thestatex(t)
evolvesa ordingtotheequationx(t) = x(t − 1) + u(t)
where
u(t)
istheinputat timet
. ThedomainsU
andX
ofu
andx
are dis reteintervals. A ostf t (x(t − 1), u(t))
is asso iatedwith ea h transition o urring from astatex(t − 1)
withaninput valueu(t)
at timet
. Whenthe ostis negativeitrepresentsabenet. The wholeset ofinputvaluesisto bede ided andtheinitialstate
x(0)
aswell. Wewantto leadthesystemto agivennalstatex
byasequen eoftransitionsof minimum ost(ormaximumbenet).Step 1: sequen ing the de isions. In this problem there is an obvious orresponden e between the
de isionpro essand thedynami system. Inthis orresponden e thesequen eof de isionsisthe sequen e
ofinputvaluestobe hosen. Sothereisade isionforea hpointin time
t ∈ 1, . . . , T
.Step 2: dening the state. Owing to theabovementioned orresponden e,the statein dynami pro-
gramming orresponds with the state of the dynami system. Hen e the states have the following form:
{x, t}
,wherex
indi atesthestateofthesystemandt
indi atesthepointin time. The ostasso iatedwithea hstate
{x, t}
is indi atedbyc(x, t)
: itindi ates theminimum ost thatmust bepaid forrea hingstatex
attimet
.Step 3: labelextension.
•
Initialization:c(x, 0) = 0 ∀x ∈ X
.•
Extension:c(x, t) = max u∈U {c(x − u, t − 1) + f t (x − u, u)} ∀x ∈ X ∀t ∈ 1, . . . , T
.Theminimum ostis
c(x, T )
(ifitnegative,itrepresentsamaximumbenet).Complexity. The numberof possiblevaluesfor
x
is|X|
, while the numberof possible valuesfort
isT
.Hen e thenumberofstatesgrowsas
O(|X|T )
. Whenextendinglabels,thenumberofprede essorsforea h stateis|U |
. Hen etheworst- asetime omplexityoftheD.P.algorithmisO(|X||U |T )
. The omputational omplexityispseudo-polynomial.A numeri alexample. Tables6representsaninstan eoftheproblemwith
X = {1, 2, 3}
,U = {−1, 0, 1}
and
T = 3
. Thesystemisrequiredtorea hstatex = 2
att = 3
. Thestates-transitionsgraphisrepresentedf 1 f 2 f 3
-1 0 1 -1 0 1 -1 0 1
1 2 -7 -3 1 -5 -9 0 -6 -4
2 0 5 -4 -2 -14 2 1 -1 0
3 3 -10 -3 15 20 -8 4 -9 -2
Table6: Thetransition osts. Rowsindi ate the
x
value, olumnsindi atetheu
value.in Figure12togetherwiththelabelsandtheoptimalsolution.
1,0
2,0
3,0
1,1
2,1
3,1
1,2
2,2
3,2
2,3 0
0
0
-7
-3
-10
-12
-17
-1
-18 -7
-3 0
5
-4 3
-10
-5
-9 -2
-14
2 15
20
-4
-1
4
Figure 12: The state-transition graph and the state extensions. Costs are represented in blue; optimal
prede essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.
The problem. We are given a set
P = {1, . . . , n}
of proje ts and a budgetR
. We have to assign aninvestment to ea h proje t. Depending on the investment, ea h proje t is expe ted to yield a prot. No
assumptionismadeaboutthekindofrelationshipbetweentheinvestmentandtheprot,but forsimpli ity
hereweassumethattheinvestmentsareintegerandnon-negative. Forea hproje t
i ∈ P
the orresponding investmentisrepresentedbyx i
and the orrespondingexpe tedprotbyf i (x i )
. Thedomain ofx i
, i.e. theset of possibleinvestments in proje t
i ∈ P
is indi ated byX i
. Theobje tive is to maximize the overallexpe tedprotwithoutex eedingthebudget.
Step 1: sequen ing the de isions. Inthis problem we onsider theproje tsin asequen e, arbitrarily.
At ea h point in time during the de ision pro ess therst part of the sequen ehas already beens anned
while thelastpartofthesequen eis not,i.e. therstproje tshavebeenassigned aninvestmentwhilethe
investmentsin the remainingproje tsarestill to bede ided. Soade isionmust be takenforea h proje t
i ∈ P
.Step2: deningthestate. Thestatemustrepresentallrelevantinformationatanygeneri stepduring
thede isionpro ess. Obviouslyweneedto knowwherewearein thede isionpro ess, i.e. whi histhelast
de ided investment. Furthermore, owingto the onstraint onthe limitedbudget
R
, weneed to know howmu h resour e is left. Hen e the states have thefollowing form:
{i, r}
, wherei
indi ates the last proje tonsidered and
r
indi ates the residual available budget. The prot asso iated with ea h state{i, r}
isindi ated by
p(i, r)
: it indi ates themaximum prot that anbe a hieved when rea hing state{i, r}
. Anadditionalinitialstate
{0, R}
orrespondstothebeginningofthede isionpro ess,whennoinvestmenthas beende idedyetandthewhole budgetisstillavailable.Step 3: labelextension.
•
Initialization:p(0, R) = 0
.•
Extension:p(i, r) = max x i ∈X i {p(i − 1, r + x i ) + f i (x i )} ∀i ∈ P ∀r ∈ 0, . . . , R
.The maximum overall expe ted prot is
max R r=0 {p(n, r)}
. If the expe ted prots are largerthan the in-vestments (i.e.
f i (x i ) ≥ x i ∀i ∈ P ∀x i ∈ X i
) and it is possible to invest all the resour e (i.e.R ≤ P
i∈P max x i ∈X i {x i }
), then themaximum expe ted protis ertainly attained at state(n, 0)
, be auseit isertainlyoptimaltoinvestthewholebudget.
Complexity. Thenumberofpossiblevaluesfor
i
isn
, whilethenumberofpossiblevaluesforr
isR + 1
(from
0
toR
). Hen e thenumberofstatesgrowsasO(nR)
. Whenextendinglabelstoea hstateofproje ti ∈ P
,thenumberofprede essorsforea hstateisatmost|X i |
,whi h annotbelargerthanR+ 1
. Hen etheworst- asetime omplexityoftheD.P.algorithmis
O(nR 2 )
. The omputational omplexityofthisalgorithm ispseudo-polynomial.P = {1, . . . , 4}
andR = 10
.x 1 f 1 x 2 f 2 x 3 f 3 x 4 f 4
0 0 0 -2 0 0 0 -5
1 7 1 4 1 5 1 -2
2 13 2 7 2 6 2 3
3 17 3 8 3 7 3 7
4 20 4 8
Table7: Thepossibleinvestmentsandthe orrespondingexpe tedprotsforea hproje t.
Thestates-transitionsgraphisrepresentedinFigure13togetherwiththelabelsandtheoptimalsolution.
0,10 1,10
1,9
1,8
1,7
1,6
2,7
2,6
2,5
2,4
2,3
3,3
3,2
3,1
3,0 4,0
0 0
7
13
17
20
17
21
24
27
28
32
33
34
35 39
0
7
13
17
20
8
7
8
4
7
8
-2
4
7
8
-2
4
7
8
8
7
8
6
7
8
5
6
7
8
0
5
6
7
7
3
-2
-5
Figure 13: The state-transition graph and the state extensions. Costs are represented in blue; optimal
prede essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.
The problem. Averysmall arrental ompanythereisonlyone ar. The ompanyhas olle tedaset
N
of ordersfrom potential ustomers andnowitmustde idewhi h ordersto satisfyinorder to maximizeits
prots. Ea horder
i ∈ N
is hara terizedbyastarttimes i
,anend timee i
andaprotp i
. Obviously,notwosele tedorders anoverlapin time.
Remark.Ingraphterminologythisproblemis alledMaxindependentsetproblemonanintervalgraph.
We andeneagraphwhereea hvertex orrespondstoanorderandanytwoverti es
i
andj
are onne tedby an edge if and only if thetwo orresponding orders overlap. For its parti ular stru ture, the resulting
graphis alledinterval graph. Overlappingordersarein ompatible,i.e. they annotbebothsele ted. This
onstraint translates into the sear h for an independent set, i.e. a subset of verti es su h that they are
not onne tedto oneanotherby any edge. Thesubsetof orders yielding themaximumprot orresponds
to a maximum weight independentset, after assigning ea h vertex
i
a weight equalto the protp i
of theorrespondingorder. Themaxindependentsetproblemis
N P
-hardongeneralgraphs,butitispolynomially solvableonintervalgraphs.Step 1: sequen ing the de isions. The orders an be sequen ed a ording to their start time
s
. Abinaryde isionmustbetakenforea hofthem(whether tosele tthatorderornot).
Step 2: deningthe state. Atea hpointalongthede isionpro essweneedtoknowwhereweare,i.e.
whi histhelastorder onsideredandwhat onstraintsarepropagatedtothefuturede isionsbe auseofthe
de isionsalreadytaken. Thisiseasilyrepresentedbythetimewhenthe arbe omesavailable. A tuallythe
timethe arbe omesavailableisnotdire tlyrelevantinitself;whatisrelevantisthenextorderthat anbe
sele ted. Ifweknowwhi histhenextorderthat anbesele tedwedonotevenneedtoknowwhi h isthe
lastorder onsidered.Hen ethestateshavethefollowing(verysimple)form:
{i}
,wherei
indi atesthenextorderthat anbesele tedwhenthe arbe omesavailableagain. Theprotasso iatedwithea hstate
{i}
isindi atedby
f (i)
: itindi atesthemaximumprotthat anbea hievedwhenrea hingstate{i}
. Adummystate
{n + 1}
representsthenalstate,whenallordershavebeende ided. Wesets n+1
toanarbitraryvaluelargerthan
max i∈N {e i }
.Step 3: labelextension.
•
Initialization:f (1) := 0
.•
Extension:f (i) := max{0, max j∈N:e j ≤s i {f (j) + p j }} ∀i = 1, . . . , n + 1
.Themaximumprotis
f (n + 1)
.Complexity. Thenumber ofpossiblevaluesfor
i
isn + 1
. Whenextendinglabelsto ea h state{i}
, thenumber of prede essors is at most
n
. Hen e the worst- ase time omplexity of the D.P. algorithm is notworse than
O(n 2 )
. However, it is redundant to explore all prede essors for ea h state. A more e ient implementationisobtainedifweassignea hstatej
auniquesu essorsucc(j)
su hthatsucc(j) = argmin
iinN:s i ≥e j
{s i }.
Theorder
succ(j)
isthe rstorderthat anbesele tedafter orderj
. Ifwe andeterminesucc(j)
forea hj ∈ N
,thenwe an onstru tagraphinwhi hea hstatej
hasonlytwooutgoingar s: anar withvalue0
tothenextstate
j + 1
andanar ofvaluep j
tosucc(j)
. Thesetwoar srepresentthetwoalternatives: sele tj
ordo notsele tj
. Theresultinggraphisdire ted,a y li andlayeredandhasonlyO(n)
ar s: thereforethelabelpropagation algorithmtakes
O(n)
. The bottlene k determiningtheworst- asetime omplexity is the onstru tion ofthegraph. It an bedonein lineartimeif theordersare sorted,ashownin Algorithm10.1. Iftheyarenot, ittakes
O(n log n)
tosort themand thereforethisis theresultingtime omplexity ofthealgorithm.