kmedian/kmedian.html

<html>

  <head>
    <title>
      KMEDIAN - A Program for the K-Medians Problem
    </title>
  </head>

  <body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">

    <h1 align = "center">
      KMEDIAN <br> A Program for the K-Medians Problem
    </h1>

    <hr>

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

    <h3 align = "center">
      Languages:
    </h3>

    <p>
      <b>KMEDIAN</b> is available in
      <a href = "../../f77_src/kmedian/kmedian.html">a FORTRAN77 version</a> and
      <a href = "../../f_src/kmedian/kmedian.html">a FORTRAN90 version</a>.
    </p>

    <h3 align = "center">
      Related Data and Programs:
    </h3>

    <p>
      <a href = "../../f_src/kmeans/kmeans.html">
      KMEANS</a>,
      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;
    </p>

    <h3 align = "center">
      Reference:
    </h3>

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

    <h3 align = "center">
      Source Code:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "kmedian.f90">kmedian.f90</a>, the source code.
        </li>
        <li>
          <a href = "kmedian.sh">kmedian.sh</a>,
          commands to compile the source code.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      Examples and Tests:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "co04_main.txt">co04_main.txt</a>,
          the main input file.
        </li>
        <li>
          <a href = "co04_dist.txt">co04_dist.txt</a>,
          a set of intercity distances.
        </li>
        <li>
          <a href = "co04_weight.txt">co04_weight.txt</a>,
          a set of weights or costs associated with the cities.
        </li>
        <li>
          <a href = "kmedian.dat">kmedian.dat</a>,
          an output file.
        </li>
        <li>
          <a href = "kmedian.out">kmedian.out</a>,
          the output from a run of the sample program.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      List of Routines:
    </h3>

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

    <p>
      You can go up one level to <a href = "../f_src.html">
      the FORTRAN90 source codes</a>.
    </p>

    <hr>

    <i>
      Last revised on 27 November 2006.
    </i>

    <!-- John Burkardt -->


  </body>

  <!-- Initial HTML skeleton created by HTMLINDEX. -->

</html>