KMEDIAN
A Program for the K-Medians Problem

KMEDIAN is a FORTRAN90 program which seeks solutions to the K-Medians problem, by G Cornuejols, M L Fisher, G L Nemhauser.

Languages:

KMEDIAN is available in a FORTRAN90 version.

Related Data and Programs:

KMEANS, a FORTRAN90 library which contains several different algorithms for the K-Means problem, which organizes a set of N points in M dimensions into K clusters;

Reference:

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

Source Code:

• kmedian.f90, 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.txt, the output file.

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.