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