My solution to the metric k-center (NP Complete) problem
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
lib
runner
viewer
.gitignore
.sublime-project
.sublime-project.sublime-workspace
Project6.pdf
README.md
notes

README.md

Metric k-Center

This is my solution to the NP-Complete problem, metric k-center. A full description of the problem can be found on wikipedia.

I'm currently working on two separate peices, the runner and the viewer. The runner is a comand-line program that will do the actual hard work of solving the problem (or estimating a solution, to be more exact) and the viewer will display the resutls of each iteration in a graphical format. I've described the struture a little more regarding each component below.

Runner

The runner is written in JRuby and is operated from the command line. This simplifies the model greatly (not having to deal with a UI). Furthermore, I am using JRuby because of the benefits of threading (REAL threading) over the MRI or REE VMs. Since the goal of the problem is to minimize k, this allows us to solve for multiple k's simultaneously.

Viewer

You can imagine that if we are solving for multiple values of k and performing M evolutions in our genetic algorithm (where M can be upwards of 1,000) that we will have lots of intermediary solutions. As such, it may not be a great idea to generate visual representations for each of these as we go along. It might be better to view these, selectively, after the runner as completed.

Well, that is exactly what we're going to do. The runner will store each intermediary result in the DB in a textual format. The viewer is a web app that allows you to select a run and a particular point in the run and then you can visualize the results via JavaScript rendering in-browser.

Test Generator

Obviously, there needs to be some test data to ensure that the program is running as expected. As such, the lib/ directory contains a simple command-line utility that can generate some test data of any specified size. Some pre-built test files have already been generated and stored under the runner/test directory.