KMEDIAN
A Program for the K-Medians Problem

KMEDIAN is an executable FORTRAN90 program, using single precision arithmetic, for the K-Medians problem.

Reference:

1. Gerard Cornuejols, Marshall Fisher, George Nemhauser,
   Location of Bank Accounts to Optimize Float, an Analytic Study of Exact and Approximate Algorithms,
   Management Science,
   Volume 23, Number 8, 1977, pages 789-810.

Related Data and Programs

KMEDIAN is also available in a FORTRAN77 version.

Source Code:

• kmedian.f90, the source code.
• kmedian.csh, commands to compile the source code.

Examples and Tests:

• co04_main.txt, the main input file.
• co04_dist.txt, a set of intercity distances.
• co04_weight.txt, a set of weights or costs associated with the cities.
• kmedian.dat, an output file.
• kmedian.out, the output from a run of the sample program.

List of Routines:

• MAIN is the main program for KMEDIAN.
• BUBBLE_SORT_A ascending sorts a real vector using bubble sort.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DIST_READ reads a distance matrix from a file.
• GET_UNIT returns a free FORTRAN unit number.
• GREEDY finds a (nonoptimal) solution using a greedy algorithm.
• I4_SWAP swaps two I4's.
• MAIN_READ_DIST reads the name of the distance file from the main file.
• MAIN_READ_SIZE reads the problem size N from the main file.
• MAIN_READ_WEIGHT reads the name of the weight file from the main file.
• R4_SWAP swaps two R4's.
• S_EQI is a case insensitive comparison of two strings for equality.
• SOL takes one step of the iteration.
• S_TO_I4 reads an I4 from a string.
• S_TO_R4 reads an R4 from a string.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• WEIGHT_READ reads weights from a file.
• WORD_NEXT_READ "reads" words from a string, one at a time.

You can go up one level to the FORTRAN90 source codes.