New results on minimax regret single facility ordered median location problems on networks

New Resul s on Minimax Reg e Single Facili y O de edMedianLoca ionP oblemson Ne wo ks Jus o Pue o, An onio M. Rod iguez-Chia, and A ie Tami 1Facul ad de Ma em´a icas. Uni e sidad de Se illa 2Facul ad de Ciencias. Uni e sidad de C´adiz 3School o Ma hema ical Sciences. Tel A i Uni e si y Abs ac . We conside he single acili y o de ed median loca ion p ob- lem wi h unce ain y in he pa ame e s (weigh s) defining he objec i e unc ion. We s udy wo cases. In he fi s case he unce ain weigh s be- long o a egion wi h a fini e numbe o ex eme poin s, and in he second case hey mus also sa is y some o de cons ain s and belong o some box, (con ex case). To deal wi h he unce ain y we apply he minimax eg e app oach, p o iding s ongly polynomial ime algo i hms o sol e hese p oblems. Keywo ds: Analysis o algo i hms, ne wo ks, acili y loca ion. 1 In oduc ion The defini ion o an ins ance o an op imiza ion p oblem equi es he specifi- ca ion o he p oblem pa ame e s, like esou ce limi a ions and coefficien s o he objec i e unc ion in a linea p og am, o edge capaci ies in ne wo k flow p oblems, which may be unce ain o imp ecise. Unce ain y/imp ecision can be s uc u ed h ough he concep o a scena io which co esponds o an assignmen o plausible alues o he model pa ame e s. In gene al, he se o all admissible scena ios may depend on he p ope ies o he unde lying model, and on some possible known ela ionships be ween he model pa ame e s. Ne e heless, we no e ha in mos published s udies i has been assumed ha each pa ame e can independen ly ake on alues in some p especified in e al. This is he so called in e al da a app oach. One o he mos common app oaches o deal wi h unce ain da a is h oughou he minimax absolu e eg e c i e ion. In his app oach he goal is o minimize he wo s case oppo uni y loss, defined as he diffe ence be ween he achie ed objec i e- unc ion alue and he op imal objec i e- unc ion alue unde he e- alized scena io. We e e he eade o [2,3,5,8,12,17], whe e ecen esul s on his subjec o gene al op imiza ion p oblems a e desc ibed. Pa ially suppo ed by g an s n. MTM2004-0909, SAB2005-0095, P06-BFM-01366, MTM2007-67433-C02. L. A ge and E. Welzl (Eds.): ESA 2007, LNCS 4698, pp. 230–240, 2007. c Sp inge -Ve lag Be lin Heidelbe g 2007 New Resul s on Minimax Reg e Single Facili y OM Loca ion P oblems 231 We we e mo i a ed by acili y loca ion op imiza ion p oblems whe e he exac na u e o he op imali y c i e ia was unce ain. Conside , o example, a loca ion model in which he cen al adminis a ion subsidizes he anspo a ion cos o he use s only a e he es ablishmen o a se e . Hence, a he momen when he acili y has o be es ablished, i is no ye clea wha is he cos unc ion ha he cen al adminis a ion will apply o de e mining he magni ude o he subsidy. The adminis a ion may decide ha he subsidy will be p opo ional o he dis ances a eled o he acili y by all he cus ome s wi h he excep ion o some unknown subse o ou lie s, e.g., hose cus ome s who a e oo close o oo a o he se e . The unce ain y is in he size o he exac defini ion o he se o ou lie s. In such a case, he c i e ion o be chosen ‘a p io i’ o he loca ion o he se e migh be aken as minimizing he eg e o he decision among a ce ain amily o c i e ia. The app oach ha we sugges o deal wi h his unce ain y is o limi ou sel es o ce ain amilies o objec i e unc ions, and apply he app oach o minimizing he maximum eg e wi h espec o he selec ion o an objec i e wi hin he p e- specified. Ou app oach is diffe en om he app oach in he exis ing li e a u e on minimax eg e acili y loca ion models, whe e he objec i e unc ion used is usually assumed o be known and ce ain ([4,5]). Specifically, in his pape , we will es ic ou sel es o he amily o o de ed median unc ions (OMF) which has been s udied ex ensi ely in he las decade in loca ion heo y, see [9,15]. This amily unifies la ge a ie y o c i e ia used in loca ion modeling. The OMF is a eal unc ion defined on Rnand cha ac e ized by a sequence o eals, λ=(λ1, ..., λn). Fo a gi en poin z∈Rn,le ¯z∈Rnbe he ec o ob ained om zby so ing i s componen s in nondec easing o de . In he con ex o a single acili y (se e ) loca ion model wi h ndemand poin s, he OMF objec i e is applied as ollows. Le xdeno e he loca ion o he se e in he espec i e me ic space, and le z(x) deno e he ec o o he nweigh ed dis ances o he demand poin s o he se e a x. The alue o he o de ed median objec i e a xis hen defined as he scala p oduc o λwi h ¯z(x). As no ed abo e, his unc ion unifies and gene alizes he classical and mos common c i e ia, i.e., cen e and median, used in loca ion modeling. (We ge he median objec i e when λi=1,i=1, ..., n, and he cen e objec i e when λi=0,i=1, ..., n −1 and λn= 1.) Ano he impo an case is he k-cen um objec i e, whe e he goal is o minimize he sum o he k-la ges weigh ed dis ances o he se e . This case is cha ac e ized by λi=0,i=1, ..., n −k,andλi=1,i=n−k+1, ..., n. In addi ion o he abo e examples, he o de ed median objec i e gene alizes o he popula c i e ia o en used in acili y loca ion s udies, e.g., cen dian and (k1,k 2)- immed mean. In his pape , we sol e a a ie y o single acili y minimax eg e o de ed median p oblems on gene al ne wo ks finding bes solu ions on each edge. The eade can find u he de ails in [16]. A summa y o he esul s is gi en in Table 1. The pape is o ganized as ollows. In Sec ion 2, we p esen he single acili y o de ed median p oblem in gene al ne wo ks. Sec ion 3 in oduces he minimax 232 J.Pue o,A.M.Rod ´ıguez-Ch´ıa, and A. Tami Table 1. Summa y o esul s Objec i e unc ion Complexi y OMF wi h lowe and uppe bounds O(m2n4log n) (k1,k 2)- immed mean O(mn4) k-cen um O(mn2log2n) Con ex OMF wi h lowe and uppe bounds O(m2n6log4n) Con ex OMF wi h lowe and uppe bounds on ees O(n6log4n) eg e o de ed median p oblem and some esul s conce ning he con exi y o he objec i e unc ion. In Sec ion 4, we de elop s ongly polynomial algo i hms o his ype o p oblems when he easible egion o he λ-weigh s has a fini e numbe o ex eme poin s. Sec ion 5 is de o ed o analyze he con ex case, which is defined by he p ope y ha he λ-weigh s a e gi en in nondec easing o de ; o his case a s ongly polynomial algo i hm is de eloped. 2No a ion Le G=(V,E) be an undi ec ed g aph wi h node se V={ 1, ..., n}and edge se E,|E|=m.Eachedgee∈E, has a posi i e leng h le,andisassumed o be ec ifiable. In pa icula , an edge eis iden ified as an in e al o leng h le,so ha we can e e o i s in e io poin s. Le A(G) deno e he con inuum se o poin s on he edges o G. Each subg aph o Gis also iewed as a subse o A(G), e.g., each edge e∈Eis a subse o A(G). We e e o an in e io poin on an edge by i s dis ance along he edge o he nodes o he edge. The edge leng hs induce a dis ance unc ion don A(G) and hus A(G)isa me ic space , see [18]. We conside a se o nonnega i e weigh s {w1,...,w n}, called w-weigh s, whe e wi,i=1,...,n, is associa ed wi h node iand ep esen s he in ensi y o he demand a his node. Fo any x∈A(G), le σ=σ(x) be a pe mu a ion o he se {1,...,n} sa is ying wσ1d( σ1,x)≤... ≤wσnd( σn,x).Fo i=1,...,n,deno ed(i)(x)= wσid( σi,x). (d(i)(x)isani- h smalles elemen in he se {wjd( j,x)}j). Fo a gi en ec o λ=(λ1,...,λ n) wi h eal componen s, called λ-weigh s, he o de ed median unc ion on A(G) is defined as λ(x):= n  i=1 λiwσid( σi,x). The single acili y o de ed median p oblem is o minimize λ(x)o e A(G), [15]. An o de ed median unc ion is called con ex i 0 ≤λ1≤...≤λn. Apoin x∈A(G)isanequilib ium poin wi h espec o a pai o nodes k, l,k=l,i wkd( k,x)=wld( l,x). A poin x∈A(G)isabo leneck poin i o some i=1,...,n,wi hwi>0, and e∈E,xis he unique maximum poin o he (conca e) unc ion wid( i,y)whenyis es ic ed o be in e.Deno ebyEQ he se o all equilib ium and bo leneck poin s. This se can be a con inuum se New Resul s on Minimax Reg e Single Facili y OM Loca ion P oblems 233 e en in he case o a ee ne wo k when wo nodes a e equally weigh ed. Le EQ be he se consis ing o he nodes o Gand all he bounda y poin s o EQ.Le B be he subse consis ing o he nodes o Gand he bo leneck poin s in EQ.Fo each e∈Edefine EQ(e)=EQ∩eand B(e)=B∩e.No e ha |EQ(e)|=O(n2) and |B(e)|=O(n). Fo each e∈E he poin s in EQ(e)(B(e)) induce a pa i ion o he edge e in o |EQ(e)|−1(|B(e)|−1) subedges. These subedges (subin e als) a e iewed as consecu i e subin e als o he ec ified edge (in e al) e. A e compu ing he dis ances be ween all he nodes, he effo o compu e and so he poin s in EQ(e)(B(e)) o each e∈Eis O(n2+|EQ(e)|logn) (O(n+|B(e)|log n)). No e ha o each subin e al in he pa i ion induced by B(e), each unc ion wid( i,x) is linea . Mo eo e , o each open subin e al in he pa i ion induced by EQ(e), no pai o unc ions in he collec ion {wid( i,x)}i in e sec . 3 The Minimax Reg e O de ed Median P oblem We assume ha he ec o λis unknown and can ake on any alue in some compac se Λ⊂Rn.Anyλ∈Λis called a scena io and ep esen s a possible λ−weigh ins ance. The minimax eg e o de ed median op imiza ion p oblem is o mally defined by: min x∈A(G)R(x):=max λ∈Λmax y∈A(G) λ(x)− λ(y). Fo any choice o he λ-weigh s, EQ con ains a leas one op imal solu ion o he espec i e o de ed median p oblem, [15]. Thus, o a gi en x∈A(G) max y∈A(G) λ(x)− λ(y)=max y∈EQ  λ(x)− λ(y)= λ(x)− λ(y∗(λ)), whe e y∗(λ)∈EQ is a minimize o λ(u)wi hu∈A(G). Fo each fixed y∈A(G) define Ry(x)=max λ∈Λ λ(x)− λ(y).(1) By defini ion, o a gi en pai x, y ∈A(G) he unc ion λ(x)− λ(y) is linea in λ. The e o e, Ry(x)= max λ∈ex (CH(Λ))  λ(x)− λ(y),whe e CH(Λ) is he con ex hull o Λand ex (CH(Λ)) is he se o ex eme poin s o CH(Λ). Wi h his no a ion R(x)=max y∈EQ Ry(x).(2) Conside an edge e∈Eand le xe 1< ... < x e q(e), be he sequence o equi- lib ium poin s in EQ(e). (q(e)=|EQ(e)|.) Simila ly, le ¯xe 1< ... < ¯xe b(e),be he sequence o bo leneck poin s in B(e). (b(e)=|B(e)|.) (See Figu e 1). F om he defini ion o equilib ium and bo leneck poin s and he abo e no a ion, we clea ly ha e he ollowing esul s. 234 J.Pue o,A.M.Rod ´ıguez-Ch´ıa, and A. Tami Lemma 1. Conside a subedge [xe k,x e k+1],1≤k<q(e). Fo any λ∈Λ, he unc ion λ(x)is linea on he subedge. Fo any y∈EQ he unc ion Ry(x)is con inuous and con ex on he subedge. Mo eo e , i he numbe o ex eme poin s o CH(Λ)is fini e Ry(x)is also piecewise linea on he subedge. Lemma 2. Fo any y∈EQ, he unc ion λ(y)is linea in λ.Le P⊆A(G) be a pa h such ha λ(x)is con ex on P o any λ∈Λ. Then o any y∈EQ he unc ion Ry(x)is con ex on P. Mo eo e , he unc ion R(x)is con ex on P. To sol e he minimax eg e o de ed median p oblem on a gene al ne wo k we will find he bes local solu ion on each edge, i.e., we will sol e msubp oblems. We e e o each local subp oblem as a es ic ed subp oblem. d(1)(y) d(2)(y) d(3)(y) d(4)(y) d(1)(x) d(2)(x) d(3)(x) d(4)(x) d(1)(x) d(2)(x) d(3)(x) d(4)(x) d(1)(x) d(2)(x) d(3)(x) d(4)(x) x1x2x4 x3x5x6 ¯x1¯x3 ¯x2¯x4 z1 1z1 2z1 3z2 1z2 2z2 3z5 1z5 2 i j || || || | ||||||| Fig. 1. Equilib ium and bo leneck poin s 4 Specific Models In his sec ion, we ocus on sol ing es ic ed subp oblems o a a ie y o se s Λ, whe e he numbe o ex eme poin s o he con ex hull o Λis fini e. As no ed abo e, we concen a e on finding he bes solu ion on each edge. Hence, we ocus on op imizing R(x)onagi enedgee. We s a wi h he case whe e Λ={(λ1,...,λ n):ai≤λi≤bi,i=1,...,n}. The eade may no ice ha his ype o se s is he mos common one used in he li e a u e on eg e analysis, see [12]. He e, we can s eng hen he esul in Lemma 1. Conside an edge e∈E. Lemma 3. Fo each 1≤k<q(e),andanyy∈EQ he unc ion Ry(x)is he maximum o nlinea unc ions in [xe k,x e k+1]. New Resul s on Minimax Reg e Single Facili y OM Loca ion P oblems 235 Lemma 4. Fo each 1≤k<q(e), he unc ion R(x)is he uppe en elope o O(n|EQ|)linea unc ions o all x∈[xe k,x e k+1]. To sol e he es ic ed p oblem on an edge e,wefi s dosomep ep ocessingon his edge. Assume ha we ha e al eady compu ed and so ed he equilib ium poin s in EQ(e). Fo each iple y∈EQ, i, j∈V, we compu e he a mos wo oo s o he equa ion wid(x, i)=wjd(y, j)one. Define BP(e) obe he se consis ing o EQ(e) and all hese oo s. |BP(e)|=O(n2|EQ|). Mo eo e , o each ile zk i(y) be he solu ion, i i exis s, o he equa ion d(i)(x)=d(i)(y)(in he a iable x), in he in e al [xe k,x e k+1]. Each poin zk i(y), is in BP(e).) Finally, we so he elemen s in BP(e). The o al p ep ocessing effo is O(n2|EQ|log n). Co olla y 1. A e spending O(n2|EQ|logn) ime on p ep ocessing, o each 1≤k<q(e) he local minimize o R(x)o e he in e al [xe k,x e k+1]can be compu ed in O(n|EQ|) ime. The op imal solu ion o he minimax eg e o de ed median p oblem on he edge ecan be compu ed in O(n|EQ||EQ(e)|) ime. The abo e esul implies ha o a gene al ne wo k he o al ime o sol e he minimax eg e o de ed median p oblem o e a box is O(m2n5). The la e bound can be u he imp o ed. Focusing on a gi en edge, we dynamically main ain [11] he uppe en elope o O(|EQ|) linea unc ions which define he unc ion R(x) o e a efined subin e al defined by wo consecu i e elemen s in he se BP(e). Specifically, ollowing he o de ing o he elemen s in BP(e)weupda e his en elope. Fo a gi en elemen u∈BP(e), i u∈EQ(e) we may need o upda e O(|EQ|) linea unc ions since he o de ing o some o he slopes o he unc ions {d(i)(x)}change. (Fo each y∈EQ we need o upda e a mos wo elemen s, pe pai o indices j, k such ha wjd( j,u)=wkd( k,u), in he sequence {d(i)(x)−d(i)(y)}i, o change he slope o a d(i)(x) unc ion, pe each jsuch ha uis he maximum o he unc ion wjd( j,x)one.) I ucoincides wi h some elemen zk i(y) defined abo e, we need o upda e one unc ion, pe each y∈EQ and j, k such ha wjd( j,u)=d(i)(u)=d(i)(y)=wkd( k,y), in he collec ion. Thus, he o al numbe o inse ions and dele ions o unc ions o he collec ion o O(|EQ|) unc ions in he uppe en elope is O(|EQ|n2). Using he da a s uc u e in He shbe ge and Su i [11], each inse ion and dele ion can be pe o med in O(log n) ime. Also, he minimum o R(x) o e each subin e al connec ing wo consecu i e elemen s o BP(e) can be compu ed in O(log n) ime. Since he e a e O(n2)poin sinEQ(e)andO(n2|EQ|)poin sinBP(e) he o e all effo o find he bes solu ion on eis O(n2|EQ|log n). Theo em 1. The o al ime o sol e he single acili y minimax eg e o de ed median p oblem o e a box on a gene al g aph is O(m2n4logn). We no e ha in some impo an cases he numbe o ex eme poin s o he con ex hull o Λis ela i ely small. Hence, i may be ad an ageous o conside hese ex eme poin s explici ly. This is he case o he amily o (k1,k 2)- immed mean unc ions [15], men ioned in he in oduc ion. (O he cases a e analyzed in he nex sec ion.) Fo his amily Λ={(λ1,...,λ n):∃k1,k 2;k1+k2<n,λ 1=...= 236 J.Pue o,A.M.Rod ´ıguez-Ch´ıa, and A. Tami λk1=λn−k2+1 =... =λn=0,λ k1+1 =...=λn−k2=1}.The ex eme poin s o he con ex hull o Λa e he ec o s o he o m (0,...,0,1, ...,1,0,...,0). The e o e, in o al he e a e O(n2)ex emepoin s. Conside an edge e∈E. We claim ha o his amily, on each in e al defined by wo consecu i e poin s o EQ(e), he unc ion R(x) can be desc ibed as an uppe en elope o O(n2) linea unc ions. To acili a e he discussion, o each k=1,...,n,le Sk(x)=n i=n−k+1 d(i)(x). Fo each 1 ≤s<q(e), and o each x∈[xe s,x e s+1], we ha e R(x)= max k1,k2;k1+k2<n n−k2  i=k1+1 d(i)(x)−k1,k2,whe e k1,k2=min y∈EQ n−k2  l=k1+1 d(l)(y). Hence, R(x)= max k1,k2;k1+k2<n Sn−k1(x)−Sk2(x)−min y∈EQ Sn−k1(y)−Sk2(y). Since R(x) is he uppe en elope o O(n2) linea unc ions, i s minimum on he in e al [xe s,x e s+1] can be compu ed in O(n2) ime using he algo i hm in [14]. Hence, he solu ion o he minimax eg e o de ed median p oblem on a gi en edge e o his amily o unc ions, can be ob ained in O(n2|EQ(e)|) ime. Theo em 2. The o al ime o sol e he single acili y minimax eg e (k1,k 2)- immed mean p oblem on a gene al g aph is O(mn4). 5 Minimax Reg e Con ex O de ed Median P oblem In his sec ion we analyze he minimax eg e con ex o de ed median p oblem which includes se e al in e es ing and mos common amilies o unc ions used in Loca ion Theo y. The fi s is he amily o k-cen um unc ions whe e kcan a y be ween 1 and n(see [19]). We ha e Λ={(λ1,...,λ n):λ1≤... ≤λnand λi∈{0,1},i= 1, ..., n}.Thenex eme poin s o he con ex hull o Λa e he ec o s o he o m (0,...,0,1,...,1). Conside an edge e∈E. We claim ha o his amily, on each in e al defined by wo consecu i e poin s o B(e), he unc ion R(x) can be desc ibed as an uppe en elope o ncon ex unc ions. Indeed, o each 1 ≤s<b(e), and o each x∈[¯xe s,¯xe s+1], R(x)= max k=1,...,n n  i=n−k+1 d(i)(x)−ζk,whe e ζk=min y∈EQ n  l=n−k+1 d(l)(y). Hence, R(x)= max k=1,...,n Sk(x)−min y∈EQ Sk(y). No e ha o each i=1,...,n, he unc ion d( i,x) is linea o e he subin- e al [¯xe s,¯xe s+1]. The e o e, o each k=1,...,n, he unc ion n l=n−k+1 d(l)(x) is con ex o e he subin e al [¯xe s,¯xe s+1]. (See [15,19]). New Resul s on Minimax Reg e Single Facili y OM Loca ion P oblems 237 To e alua e R(x) o agi enx, i is sufficien o so he elemen s {wid(x, i)} in o de o compu e he e ms {Sk(x)}k, and finally find maxk=1,...,n Sk(x)− miny∈EQ Sk(y). The minimum o R(x)on hein e al[¯xe s,¯xe s+1]can henbe compu ed in O(nlog2n) ime by using he pa ame ic app oach o Megiddo [13] wi h he modifica ion in Cole [7]. Hence, he solu ion o he minimax eg e o de ed median p oblem on a gi en edge e o his amily o unc ions can be ob ained in O(nlog2n|B(e)|) ime. (We assume ha in he p ep ocessing phase o he algo i hm we ha e al eady calcula ed he e ms {ζk}k. The o al effo o his phase is O(mn2log n), see [15]). Theo em 3. The o al ime o sol e he minimax eg e k-cen um p oblem on a gene al g aph is O(mn2log2n). The abo e analysis and algo i hm a e also applicable o he mo e gene al con ex case defined by Λ={(λ1,...,λ n):λ1≤...≤λnand λi∈[a, b],i=1,...,n}, whe e aand bsa is y 0 ≤a≤b,see[15].In hiscaseweha e Λ=CH({(λ1,...,λ n):λ1≤...≤λnand λi∈{a, b},i=1,...,n}). As ano he example o a con ex amily o o de ed median unc ions wi h a small numbe o ex eme poin s, conside he model co esponding o he α- cen dian p oblem, see [15]. In his case, Λ={(λ1,...,λ n):∃0≤α≤1,λ 1= ...=λn−1=α, and λn=1}.We ha e ex (Λ)={(0,...,0,1),(1,...,1)}. 5.1 The Case o In e al Weigh s and O de Cons ain s In his sec ion, we conside he minimax eg e con ex o de ed median p oblem whe e he λ−weigh s a e in he se , Λ≤={(λ1,...,λ n):λi∈[ai,b i] o i=1,...,n, and 0 ≤λ1≤...≤λn}. Wi hou loss o gene ali y, we may assume ha bo h sequences {ai}and {bi} a e nonnega i e and nondec easing. We no e ha he componen s o each ex- eme poin o Λ≤a e elemen s o he se AB ={a1,...,a n,b 1,...,b n}. Indeed, le λbe an ex eme poin and suppose wi hou loss o gene ali y ha some λi∈ AB.Le 1≤s≤i≤ ≤nbe such ha λs−1<λ s=λi=λ <λ +1. Fo ε>0 sufficien ly small, conside he ec o λ(ε+) defined by se ing λj(ε+) = λj+ε o s≤j≤ and λj(ε+) = λjo he wise. Simila ly, con- side he ec o λ(ε−) defined by se ing λj(ε−)=λj−ε o s≤j≤ and λj(ε−)=λjo he wise. The ec o λis he midpoin o he in e al connec ing λ(ε+) and λ(ε−), con adic ing he ac ha λis an ex eme poin o Λ≤. Recall ha o a gi en y∈EQ,Ry(x)=max λ∈Λ≤ λ(x)− λ(y),see(1). E alua ing R(x) o agi enxamoun s o compu ing he |EQ| alues Ry(x) o all y∈EQ,see(2). We p opose an algo i hm o compu e Ry(x) o any fixed y∈EQ.Conside an edge e∈E.Le ¯xe kand ¯xe k+1 be wo consecu i e elemen s o B(e). λ(x)isa 238 J.Pue o,A.M.Rod ´ıguez-Ch´ıa, and A. Tami con ex unc ion on [¯xe k,¯xe k+1], see [15]. By Lemma 2, he unc ions {Ry(x)}y∈EQ, as well as R(x), a e all piecewise linea and con ex on [¯xe k,¯xe k+1]. Fo a fixed y∈EQ and x∈[¯xe k,¯xe k+1] he e alua ion o Ry(x) can be done by sol ing he ollowing linea p og am: Ry(x)=maxcT(x)λ−hT(y)λ s. . λi−λi+1 ≤0,∀i=1,...,n−1, ai≤λi≤bi,∀i=1,...,n, whe e cT(x)=(d(1)(x),...,d (n)(x)) and hT(y)=(d(1)(y),...,d (n)(y)). (Recall ha he op imal solu ion λ∗sa isfies λ∗ i∈AB o i=1,...,n). Defining μi=λi−ai,βi=bi−ai, o i=1,...,n,αn=0,andαi=ai+1 −ai o i=1,...,n−1, he o mula ion abo e educes o: n  i=1 ai(d(i)(x)−d(i)(y))+ max cT(x)μ−hT(y)μ s. . μi−μi+1 ≤αi,∀i=1,...,n−1, μi≤βi,∀i=1,...,n, μi≥0,∀i=1,...,n. Se ing u0=un= 0, he o mula ion o i s co esponding dual p oblem is: n  i=1 ai(d(i)(x)−d(i)(y))+ min n  i=1 αiui+ n  i=1 βi i s. . ui−ui−1+ i≥d(i)(x)−d(i)(y),∀i=1,...,n, ui, i≥0,i=1,...,n. No ice ha he ma ix defining he abo e linea p og am is o ally unimodula since i is a flow ma ix augmen ed by he iden i y ma ix. The abo e model co esponds o he ollowing single commodi y min-cos flow p oblem. (See Figu e 2.) Fo each i=1,...,n−1, uiis he flow on he a c (i+1,i), and o each i=1,...,n, iis he flow on le -a c (0,i). Fo i=1,...,n, he demand a node iis d(i)(x)−d(i)(y). No e ha he demand can be o any sign. To accoun o he sign o he demand o i=1,...,n, define δ+ i(x)=max{0,d (i)(x)−d(i)(y)}and δ− i(x)=max{0,−(d(i)(x)−d(i)(y))}.The label a ached o each edge in he g aph has wo coo dina es. The le coo dina e is he capaci y uppe bound on he flow, and he igh one is he pe uni cos o flow on he edge. The min-cos flow p oblem is o find he minimum cos o anspo ing n i=1 δ+ i(x) uni s om he sou ce node 0 o he des ina ion n+1. The as es known s ongly polynomial algo i hm o sol e a single com- modi y min-cos flow p oblem on a ne wo k wi h nnodes and medges is O(mS(n, m)logn), whe e S(n, m) is he ime o sol e he single sou ce sho - es pa h p oblem on a ne wo k wi h nnodes and medges, ha ing nonnega i e leng hs. (See Ahuja e al. [1].) This algo i hm has O(mlog n) scaling phases, whe e in each phase a sho es pa h p oblem is sol ed in S(n, m) ime.Fo a