The LR-dispersion problem (Frontiers of Theoretical Computer Science)

The

_{LR‐dispersion problem}

Toshihiro

_Akagi

Department

of

_{Computer, Science,}

Gunma

_University

Tetsuya

Araki

Principles

of

Informatics Research

_Division,

National Institute of

Informatics

Shin‐ichi

Nakano

Department

of

_{Computer Science,}

Gunma

_University

1

Introduction

The

_facility

location

_problem

_{and many} of its variants have been

_{studied[6, 7].}

\mathrm{A}

typical problem

is to find a set of locations to

_place

facilities with the des

_gnated

cost

minimized.

_By

_contrast,

in _{this paper}weconsider the

dispersion problem,

which finds a

set of locationswith the

_designed

costmaximized.

Given aset P ofn

points,

and the distance dforeach

pair

of

points,

and an

integer

k

with

k\leq n

,wewishtofind a subsetS\subset P with

|S|=k

such that some

designated

cost

is

_maximized[1,

_{4, 5, 9, 10, 11, 12,}

_13].

Inoneof

typical

casesthe cost tobe maximizedisthe minimum distance betweentwo

points

inS. IfP isaset of

points

on the

plane

then the

problem

is

NP‐hard[ll, 13],

and

ifP is aset of

_points

onthe line then the

problem

canbe solvedin

O(\displaystyle \max\{n\log n, kn\})

time[ll, 13]

by

dynamic programming approach,

andin O

₍

n

loglog

n

)

time[1]

by

sorted

matrix search

_{method[3, 8].}

In this paper we consider two variants of the

_dispersion

_problem

on the line. Let P

be a set of

points

onthe horizontal \mathrm{h}\mathrm{n}\mathrm{e}. We wish to find asubset S\subset Pwith

|S|

=k

maximizing

cost

_(S)

defined asfollows.

Let the cost cost

_(s)

of s \in S=

_{\{s_{1}, s_{2}, . . . , s_{k}\}}

be the sum of the distance to its left

.neighbor

in S andthe distance to its

_{right neighbor}

in S. We assume s_{1}, s_{2}_,..._,s_{k} are

sortedfrom left to

_right.

_Especially

theleftmost

_{point s_{1}\in S}

has noleft

neighbor,

so we

define thecost ofs_{1} is

d(s_{1}, s_{2})

.

Similariy

thecost of the

rightmost point

s_{k}

ig

d(s_{k-1}, s_{k})

.

Andthecost

_(S)

of Sisthe

minimum

cost _{among the}costs

_{cost(sl), cost(s2),}

...

,

cost(sk).

We call the

_problem

above the LR

_{‐dispersion problem.}

An

_{O(kn^{2}\log n)}

time

_algorithm

In this paperwe

design

an

algorithm

tosolve the

LR‐dispersion problem.

Our

algorithm

runsin

O(n\log n)

time,

and based onmatrixsearch

method[3, 8].

The_{remainder of this paper is}

_organized

as follows. Section 2 contains an

algorithm

for the decision version of the

_{LR‐dispersion problem.}

Section 3

_gives

our

algorithm

for

the

_{LR‐dispersion problem.}

Section4 treats one morevariant of the

dispersion

problem.

Finally

Section5 is aconclusion.

2

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion}

In this section we

_give

a linear time

algorithm

to solve a decision version of the LR‐

dispersion

problem.

Givenaset

P=\{p_{1}, p_{2}, . . . , p_{n}\}

of

points

on ahorizontal

line,

andtwonumbers k and

$\lambda$we wishtodecide ifthere existsasubset S\subset P with

|S|=k

andcost

(S)\geq $\lambda$

. Wecall

the

_problem

asthe

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion problem.

We have the

_following

lemma.

Lemma 1. If

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion problem}

has a solution S =

\{s_{1}, s_{2}, . . . , s_{k}\}

\subset

P,

then

_{S'=\{p_{1}, s_{2}, s_{3}, . . . , s_{k-1},p_{n}\}}

isalso asolution of the

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion

problem.

Proof. Sincecost

_{(S)\leq cost(S')}

,ifSisasolution then

S'

isalsoasolutionandcost

(S)=

cost

_(S')

holds. \square

The

_algorithm

below is a

greedy algorithm

tosolve the

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion problem.

Notethat

_{$\omega$ st(s_{i})}

for i=3,

4,

...

,k-1 is

d(s_{i-2}, s_{i})

.

By setting

a

dummy

point

s_{0}=s_{1},

cost

_{(s_{2})}

is also

_{d(s_{2-2}, s_{2})=d(s_{1}, s_{2})}

. Also notethat cost

(k)=d(s_{k-1}, s_{k})

.

Nowwe _prove the correctness ofthe

_algorithm.

Assume for a contradiction that the

algorithm

output

NO for a

given problem

but it has asolution.

Let G =

\{g_{1}, g_{2}, . . . , g_{k'}\}

with k' < k be the

points

chosen

by

the

algorithm,

and

O=\{0_{1}, 0_{2}, . . . , 0_{k}\}

the

_points

ofa solution.

By

Lemma 1 we can assume 0_{1} =p_{1} and

o_{k}=p_{n}. Notethatg_{1}=0_{1}=p_{1} andg_{k'}=0_{k}=p_{n} hold. Wehavethe

following

twocases.

Case 1 : For all

i,

1\leq i<k',

g_{i}\leq 0_{i}

holds.

Then our

greedy algorithm

canchoose at least one more

point

0_{k'} or moreleft

point.

A contradiction.

Case 2 : Fojrsome

i,

1\leq i<k',

_{g_{i}>0_{i}} holds.

Sinceg_{2} is chosen in a

greedy

_manner, we can assume

_{g_{2}\leq 0_{2}}

. Let

j

be the minimum

such i. Since g_{j-2}

\leq 0_{j-2}

and g_{j-1}

\leq 0_{j-1}

hold,

our

greedy algorithm

choose 0_{i} or more

left

_point

as_{g_{i}}. A contradiction.

Theorem 1. One cansolve the decision versionofthe

LR‐dispersion

problem

in

O(n)

Algorithm

1 find

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion}

_{(P, k, $\lambda$)}

/*P=\{p_{1}, p_{2}, . . . , p_{n}\}

andp_{1},p_{2},...

,p_{n} are sortedfromleft to

right

*/

/*

Choose s_{1} and

s_{k}*/

s_{1}=p_{1}, s_{k}=p_{n} s_{0}=s_{1}

/*

Choose _{s_{2}, s_{3}},... ,

s_{k-1^{*}}/

c=2 for i=2 to k-1 do

while

_{d(s_{i-2},p_{\mathrm{c}})< $\lambda$}

and

_{d(p_{c},p_{n})\geq $\lambda$}

do c++

end while

if

_{d(p_{\mathrm{c}},p_{n})< $\lambda$}

then

/*_{\mathrm{n}\mathrm{o}}

solution since

_{d(p_{c},p_{n}) <$\lambda$^{*}/}

return NO

else

/*d(s_{i-2},p_{\mathrm{c}})\geq $\lambda$

hold

_{\mathrm{s}^{*}/}

s_{i}=p_{c} c++ end if endfor

/*\mathrm{O}_{\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}^{*}}/

return

_{S=\{s_{1}, s_{2}, . . . , s_{k}\}}

/*

Dumm

_{\mathrm{y}^{*}/}

3

_{LR‐dispersion}

Onecan

design

an

O(n\log n)

time

algorithm

tosolve the

_{LR‐dispersion problem,}

based

onthe sorted matrixsearch

_{method[3, 8].}

First let M be the matrix in which each _{element m_{i,j}} is

_{d(p_{i},p_{j})}

ifi

_<j

, otherwise

0. Then _{m_{i,j}}

_{\leq m_{i,j+1}}

and _{m_{i,j}}

_{\geq m_{i+1,j} always}

_holds,

so the elements inthe rows and

columns are

sorted, respectively.

The cost cost

_(S)

ofasolution S of the

LR‐dispersion

problem

issomeelement in the matrix. Weare

going

tofind the

_largest

$\lambda$ in Mforwhich

the

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion problem}

has asolution.

By

appending

a suitable number of

large enough

elements to M as the elements in

the

_topmost

rows and the

rightmost

columns we can assume n is a _power of 2. Note

that the elements in the rows and columns are still

sorted,

respectively.

Let M be the

resulting

matrix. Our

_algorithm

consists ofrounds s = 1

,

2,

...

,

\log n

, and maintains a

set

L_{s}

of

_{(non‐overlapping)}

submatrices ofM

_possibly

_containing

the

_optimal

value $\lambda$^{*}.

Hypothetically

first weset

_{L_{0}=\{M\}}

. Assumeweare now

staring

round s.

For each subset M in

L_{s-1}

we divide M into the four submatriceswith

n/2^{\mathrm{S}}

rows and

n/2^{S}

columns and

_put

them into

L_{s}

. We never copy these submatrices. We

just update

the index ofthecornerelements ofeach submatrix.

Let

_{$\lambda$_{\min}}

be the median of the lower left corner elements of the submatrices in

L_{s}.

Then forthe

$\lambda$=$\lambda$_{\min}

wesolve the

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion

problem, using

the

algorithm

in

Section2. We have the

_following

twocases.

If the

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion problem}

hasnosolution thenwe remove from

L_{s}

each sub‐

matrixwith thelowerleft cornerelement

(the

smallest

element)

_greater

than

$\lambda$_{\min}

. Since

$\lambda$_{\min}

> $\lambda$^{*}

_holds,

each removed submatrix has no chance to contain $\lambda$^{*}. Thus we can

remove atleast

_{|L_{s}|/2}

submatricesfrom

L_{s}.

Otherwise if the

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion}

_problem

has a solution then we removefrom

_{L_{s}}

each submatrix with the upper

right

corner element

(the

largest

element)

smaller than

$\lambda$_{\min}

. Since

$\lambda$_{\min}\leq$\lambda$^{*}

holds,

each removed submatrix has no chanceto contain $\lambda$^{*}. Also

if

_{L_{s}}

has _{several submatrices with the upper}

_right

corner element

equal

to

$\lambda$_{\min}

then

we remove them

_except

one from

_{L_{s}}

. Now we can observe

that,

for each “chain” of

submatrices,

which is the sequence of submatrices in

_{L_{s}}

with lower left to upper

right

diagonals

on the same

line,

the number of submatrices

(1)

having

the lower left corner

elementsmaller than

_{$\lambda$_{\min}(2)}

but

_remaining

in

_{L_{s}}

, isat most one

(since

the

\cdotelements

on

“the common

diagonal

line” are

sorted).

Thus,

if

|L_{s}|/2

>

_{D_{s}}

, where

D_{s} =2^{s+1}

is the

numberof chains

_plus

one, thenwe can removeat least

_{|L_{s}|f2-D_{s}+1}

submatrices from

L_{s}.

Similarly

let

$\lambda$_{\max}

be the median of_{the upper}

_right

corner elements of submatrices in

L_{s}

, andforthe

$\lambda$=$\lambda$_{\max}

we solve the

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion problem

and

similarly

remove

somesubmatrices from

L_{s}

. This endsround s.

Now after round

_{\log n}

eachmatrix in

_{L_{\log n}}

has

_just

one

element,

thenwe can find the

We can _{prove that} at the end of round s the number of submatrices in

L_{s}

is at most

2D_{s}

, asfollows.

First

_{L_{0}}

has 1

_submatrix,

which is less than

_{2D_{0}=4}

.

By

induction assumethat

L_{s-1}

has

_{2D_{s-1}=2\cdot 2^{S}}

submatrices.

Atroundswefirst

partite

each submatrix in

L_{s-1}

into foursubmatrices then

_put

them

into

L_{s}

. Nowthe numberofsubmatrices in

L_{s}

is at most 4 \cdot

2D_{s-1}=4D_{s}

. We havefour

cases.

Ifthe

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion}

_problem

hasnosolution for

$\lambda$=$\lambda$_{\min}

thenwe canremoveat

leastahalf ofthesubmatricesin

L_{s}

isat most

2D_{s}

,asdesired. Ifthe

( $\lambda$, k)-\mathrm{L}\mathrm{R}

‐dispersion

problem

hasasolution for

_{$\lambda$=$\lambda$_{\max}}

thenwe can removeatleastahalfof the submatrices

in

_{L_{s}}

is at most

2D_{s}

, as desired. Otherwise if

|L_{s}|/2

\leq

D_{s}

then the number of the

submatrices in

_{L_{s}}

_(even

before the

_removal)

is at most

2D_{s}

, as desired. Otherwise

(1)

afterthe check for

$\lambda$=$\lambda$_{\min}

we can removeat least

|L_{s}|/2-D_{s}

submatrices

(consisting

oftoosmall

_elements)

from

L_{s}

, and

(2)

after check for

$\lambda$=$\lambda$_{\max}

we can remove at least

|L_{s}|/2-D_{s}

submatrices

_(consisting

oftoo

_large

_elements)

from

_{L_{s}}

, sothe numberof the

remaining

submatrices in

_{L_{s}}

is at most

_{|L_{s}|-2(|L_{s}|/2-D_{s})=2D_{s}}

, as desired.

Thus at the end of round s the number of submatrices in

L_{s}

is

always

at most

_{2D_{s},}

andat the endofround

_{\log n}

the number of submatrices is at most

_{2D_{\log n}=4n.}

Now we consider the

running

time. We

implicitly

treat each submatrix as the index

of the _upper

_right

element in M and the number of lows

₍

= the number of

columns).

Except

for

_the.

calls of the linear time decision

_algorithm

for the

_{( $\lambda$, k)-\mathrm{L}\mathrm{R}}

_{‐dispersion}

problem,

we need

O(|L_{s-1}|)

=

O(D_{s-1})

time for each round _s = 1

,

2,

...

,

\log n

, and

D_{0}+D_{1}+\cdots+D_{\log n-1}

=2+4+\cdots+2^{\log n}

<

2\cdot 2^{\log n}=2n

_holds,

so this

_part

needs

O(n)

time in total.

_(Here

we usethe linear time

algorithm

tofind the

median.)

Sinceeachround calls the lineartimedecision

_algorithm

twiceandthenumberof round

is

_{\log n}

this

_part

needs

_{O(n\log n)}

time intotal.

Afterround

_{s=\mathrm{l}\mathrm{o}\mathrm{g}.n}

each matrix has

_just

oneelement. Thenwe canfind the $\lambda$^{*} among

the

_{|L_{\log n}|}

_{\leq 2D_{\log n}=4n}

elements

_by

₍₁₎

_{sorting them,}

then

₍₂₎

_performing

_binary

search withthe linear timedecision

_algorithm

at most

_{\log 4n}

times. This

_part

needs

_{O(n\log n)}

time.

Thus the total

_running

time is

_{O(n\log n)}

. With asimilar method we have solved the

(original)

dispersion

problem

in

_{O(n\log n) time[1].}

Theorem 2. One cansolve the

LR‐dispersion problem

in

O(n\log n)

time.

4

Generalization

In this section we consider one more variant of the

dispersion problem

and

give

an

algorithm

tosolve the

_problem,

whichrunsin

O(n\log n)

time. Inthe

_{original dispersion}

problem

thecostisthe minimum

_distance

betweentwo

_points

s_{i} and s_{i+1}. We

generalize

Given a set P =

\{p_{1},p_{2}, . . . ,p_{n}\}

of

points

_{on a} horizontal

line,

and the distance d

for each

_pair

of

_points,

and two

_{integers k,}

h with

_k,

h \leq n, we wish to find a subset

S=\{s_{1}, s_{2}, . . . , s_{k}\}\subset P

maximizing

cost

_(S)

defined as follows.

Lcost

_{(S)=\displaystyle \min\{d(s_{1}, s_{2})}

,

d(s_{1}, s_{3})

,..._,

d(s_{1},

s_{h} Rcost

(S)=\displaystyle \min\{d(s_{k-h+1}, s_{k})

,

d(s_{k-h+2}, s_{k})

,...

,

d(s_{k-1}, s_{k})\}

and Mcost

(S)=\displaystyle \min\{d(s_{1}, s_{1+h}), d(s_{2}, s_{2+h}), \cdots, d(s_{k-h}, s_{k})\}

then cost

_{(S)=\displaystyle \min{ L $\omega$ st(S)}

,Rcost

(S)

,Mcost

(S)}.

We call the

problem

above the h

_{‐dispersion problem.}

The

_original

_{dispersion problem}

onthe lineis the h

_{‐dispersion problem}

withh=1 and the

_{LR‐dispersion}

_problem

is the

h

_{‐dispersion}

_problem

with h=2.

Lemma 2. If

_{( $\lambda$, k)-h}

_{‐dispersion problem}

hasasolution

S=\{s_{1}, s_{2}, . . . , s_{k}\}\subset P

, then

S'=\{p_{1}, s_{2}, s_{3}, . . . , s_{k-1},p_{n}\}

is also asolution ofthe

( $\lambda$, k)-h

‐dispersion

problem.

Proof. Sincecost

_{(S)\leq cost(S')}

,if Sisasolution thenS'isalsoasolutionandcost

(S)=

cost

_(S')

holds. \square

The

_algorithm

below is a

greedy algorithm

to solve the

problem.

Now we _{prove the}

correctnessofthe

_algorithm.

Assume for acontradiction that the

algorithm

output

NO for a

given

problem

but it

hasasolution.

Let G =

\{g_{1}, g_{2}, . . . , g_{k'}\}

with k' _< k be the

points

chosen

by

the

algorithm,

and

O=\{0_{1}, 0_{2}, . . . , 0_{k}\}

the

_points

of asolution.

By

Lemma 2 we can assume _{0_{1} =p_{1}} and

o_{k}=p_{n}. Note that g_{1}=0_{1}=p_{1} andg_{k'}=0_{k}=p_{n} hold. Wehave the

following

two cases.

Case 1 : For all

_i,

1\leq i<k',

_{g_{i}\leq 0_{i}}

holds.

Thenour

greedy algorithm

canchoose atleast one more

points

0_{k'} or more left

point.

Acontradiction.

Case 2 : Forsome

i,

1\leq i<k',

_{g_{i}>0_{i} holds. Sinceg_{2}, g_{3}},...

,g_{h}arechosen ina

greedy

manner, we can assume _{g_{j}}

_{\leq 0_{j}}

for

j=2

,

3,

...

,h. Let

j

be the minimum suchi. Since

g_{j-h} \leq 0_{j-h}, g_{j\cdot-h+1}

\leq

0_{j-h+1}, .. .

, g_{\mathrm{j}-1} \leq 0_{\mathrm{j}-1}

hold,

our

greedy algorithm

choose 0_{i} or

moreleft

point

as _{g_{i}}. A contradiction.

Theorem 3. One can solve the decision version ofthe

h-\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}_{0}^{ $\eta$}\mathrm{n}

problem

in

o(n)

time.

Therefore,

similartothe

_algorithm

inSection

_3,

we can

design

O(n\log n)

time

algorithm

tosolve the h

_{‐dispersion problem.}

Theorem 4. Onecansolve the h

‐dispersion problem

in

O(n\log n)

time.

5

Conclusion

Inthis_paperwehave

presented

two

_algorithms

tosolvethe

_{LR‐dispersion problem}

and

the h

_{‐dispersion problem.}

The

_running

timeof the

_algorithms

are

O(n\log n)

.

An O

₍

n

loglog

n

)

time

algorithm

to solve the

_original

_{dispersion problem}

on the line

is

_known[1].

Can we

design

an O

(

n

loglog

n

)

time

algorithm

to solve the h

_{‐dispersion}

\displaystyle \frac{\mathrm{A}1\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}2\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{d}( $\lambda$,k)-h-\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}(P,h,k, $\lambda$)}{/^{*}\mathrm{C}\mathrm{h}\mathrm{o}\mathrm{o}\mathrm{s}\mathrm{e}s_{1}\mathrm{a}\mathrm{n}\mathrm{d}s_{k^{*}}/}

s_{1}=p_{1}, s_{k}=p_{n}

/*

Dumm

_{\mathrm{y}^{*}/}

s_{0}=s_{1}, s_{-1}=s_{1}, s_{-2}=s_{1},... ,

s_{-h+2}=s\mathrm{i}

/*

Chooses_{2}, s_{3},... ,s_{k-1}

*/

c=2

for i=2\mathrm{t}\mathrm{o}k —ldo

while

_{d(s_{i-h},p_{\mathrm{c}})}

< $\lambda$and

_{d(p_{c},p_{n})}

_{\geq $\lambda$}

do

c++ end while

if

_{d(p_{c},p_{n})< $\lambda$}

then

/*_{\mathrm{n}\mathrm{o}}

solution since

_{d(p_{c},p_{n})<$\lambda$^{*}/}

return NO

else

/*d(s_{i-h},p_{c})\geq $\lambda$ \mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{s}^{*}/

s_{i}=p_{c} c++ end if end for

/*\mathrm{O}_{\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}^{*}}/

return

_{S=\{s_{1}, s_{2}, . . . , s_{k}\}}

References

[1]

\mathrm{T}_{\mathrm{t}}

_Akagi

and S.

_{Nakano, Dispersion problem}

on the

Line,

Technical

Report,

2016‐

AL‐158‐4,

IPSJ

_(2016).

[2]

T.

_Akagi,

T. Araki and S.

Nakano,

Variants of the

_Dispersion

_Problem,

Technical

Report,

2017‐AL‐I6I‐3,

IPSJ

_(2017).

[3]

P.

_Agarwal

and M.

_Sharir,

Efficient

_Algorithms

for Geometric

_{optimization,}

Com‐

puting

Surveys,

30, pp.412‐458

(1998).

[4]

C. Baur and S. P.

_Feketee,

_{Approximation}

of Geometric

_{Dispersion Problems,}

Pro.

of APPROX

_98,

_Page

63‐75

_(1998).

[5]

B.Chandraand M. M.

_Halldorsson,

_{Approximation Algorithms}

for

_Dispersion

Prob‐

lems,

J. of

_Algorithms,

_{38, pp.438‐465}

_(2001).

[6]

Z.

_Drezner,

_Facility

Location: A

_Survey

of

_Applications

and

_Methods,

_Springer

(1995).

[7]

Z. Drezner and H. W.

_{Hamacher, Facility}

Location:

_Applications

and

_Theory,

Springer

(2004).

[8]

G.

_{Frederickson,}

_Optimal

_Algorithms

forTree

_{Partitioning,}

Proc. of SODA’91

_Pages

168‐177

_(1991).

[9]

R.

_Hassin,

S. Rubinstein and A.

_Tamir,

_{Approximation Algorithms}

for Maximum

Dispersion,

Operation

Research

_{Letters, 21, pp.133‐137}

_(1997).

[10]

T. L. Lei and R. L.

_Church,

Onthe unified

_{dispersion problem:}

Efficient formulations

and exact

_algorithms,

_European

Journal of

_Operational

_{Research, 241, pp.622‐630}

(2015).

[11]

S. S.

Ravi,

D. J. RosenkrantzandG. K.

_Tayi,

Heuristic and

_Special

Case

_Algorithms

for

_Dispersion

_{Problems, Operations}

_{Research, 42, pp.299‐310}

_(1994).

[12]

M.

_{Sydow, Approximation}

Gurantees for {\rm Max} Sum and MaxMin

_{Facility Dispersion}

with Parameterised

_{Triangle Inequality}

and

_Applications

in Result

_{Diversification,}

Mathematica

_Applicanda,

_{42, pp.241‐257}

_(2014).

[13]

D. W.

_Wang

and Y. S.

_Kou,

A

_study

onTwo GeometricLocation

Problems,

Infor‐