189Fromacomputationalviewpoint,solvingtheextendedNAPunderfutureSDis
NP-hardasprovenforPD(HartmannandSteel 2006 ). Dynamic programming algo-
rithms(DPA)optimallysolvetheNAPunderfuturePDinaspecialscenario,where
thespeciesextinctionprobabilitybecomes 0 ifitisgivenenoughresources(Pardi
and Goldman 2007 ).ForgeneralscenariosHickeyetal.( 2008 )devisedsuchaDPA
thatgivesanapproximationratioofnearly 1 comparedtotheoptimalsolution.
More recently, Billionnet ( 2013 )presentedanIPapproachfortheNAPthatruns
withinafewminutesforsimulated4,000-taxoncasesandprovidesnear-optimal
solutions,whichareonly1.2%awayfromtheoptimalsolution.Itwillbeinterest-
ingtoinvestigatehowsuchDPAandIPapproachescanbeadaptedtosolvetheNAP
under the more general SD framework.
Acknowledgments TheauthorsthankTungLamNguyenfordevelopingPDAwebservice.The
authorsalsothankRoseliPellensandPhilippeGrandcolasforinvitingustowritethischapterand
three anonymous reviewers for constructive comments. This work was supported by University of
Vienna(InitiativkollegI059-N)toO.C.andtheAustrianScienceFund–FWF(I760-B17)to
B.Q.M. and A.v.H.
Open Access This chapter is distributed under the terms of the Creative Commons Attribution
NoncommercialLicense,whichpermitsanynoncommercialuse,distribution,andreproductionin
any medium, provided the original author(s) and source are credited.
Split Diversity: Measuring and Optimizing Biodiversity Using Split Networks