r - Assignment algorithm variant -

i have square matrix in r containing distances between cities:

set.seed(3) x <- matrix(sample(1:15, 16, replace = true), nrow = 4) x #     [,1] [,2] [,3] [,4] #[1,]    3   10    9    9 #[2,]   13   10   10    9 #[3,]    6    2    8   14 #[4,]    5    5    8   13 

every row represents city courier can sent, , every column represents city package has delivered. couriers have same package, can assigned every other city. use hungarian algorithm in clue::solve_lsap() find optimal assignment total cost (in case total distance) minimized:

y <- clue::solve_lsap(x) y #optimal assignment: #1 => 1, 2 => 4, 3 => 2, 4 => 3 

however, in specific case minimize spread of distances. have been searching quite time now, , found following here in book @ page 270 (and similar here in book @ page 195):

so stated objective minimize difference between maximum , minimum assigned distance, looking for. assignment of hungarian algorithm gives following difference between maximum , minimum distance:

distances <- x[cbind(1:4, y)] max(distances) - min(distances) #[1] 7 

however, best assignment minimize new objective (this solution found brute force):

#optimal assignment minimize new objective: #1 => 2, 2 => 4, 3 => 1, 4 => 3 ynew <- c(2, 4, 1, 3) distancesnew <- x[cbind(1:4, ynew)] max(distancesnew) - min(distancesnew) #[1] 4 

so clearly, hungarian algorithm doesn't give desired solution.

now question: there existing r code finds optimal assignment minimizing objective mentioned above (the difference between maximum , minimum assigned cost value)? or maybe r code algorithm achieves similar result?

those books mentioned describe algorithm want, 1) both start solution of bottleneck assignment problem (an algorithm couldn't find r code either) , 2) implementing algorithm (and possibly bottleneck assignment algorithm) myself far ideal.