Computational Complexity

Jano Simicka's Vehicle Routing Problem
page
This problem is related to the Traveling Salesman
Problem, but more complex

The Complexity Zoo
tries to separate all the different classes into which
computationally complex problems fall, and tell why.
Nice resource!

Professor David L. Dowe of Monash University's
Mixture Modeling
large link list page. Mixture modeling seems to be a
specialization or generalization of cluster analysis.
See also his his link page on
Minimum
Message Length (variously also "Minimum Encoding
Length Inference" or "Minimum Description Length")
concerning information theoretic inference methods.

Extended Solomon's Vehicle Routing Problem with Time
Windows
test cases
by Jeorg Homberger, with the flavor of the original
test cases, but with significantly more "customers".

A large list of assorted computational complexity
bookmarks

stochastic programming bibliography

Kolmogorove complexity links page

Stas Busygin's NPCompleteness Page
This link and the next are for mirror sites. Stas
focuses on the SAT01 (satisfiability) problem, one
which maps nicely in polynomial time to many NP
problems, and has a known good approximate heuristic
solution.

Stas Busygin's NPCompleteness Page
A mirror site of the one above.

SAT01 Notes
Stas focuses on the satisfiability problem.

Stas Busygin's NPCompleteness Page
Stas' reading list.

Analysis of algorithms, complete class notes, with code.

Turing Machine Simulator

A compendium of NP optimization problems

The Electronic Journal of Combinatorics

The Last Homely Page

JAVA combinatorial optimization

e82a_11_2414.pdf
Internet Based Hierarchical [VLSI] Floor Plan Design.

Adaptive Simulated Annealing 20.2

Rachel Moldover and Paul Coddington,
Improved Algorithms for Global Optimization
Compressed Postscript file.

TesiOnLine  Homepage Tesi
Simulated annealing stuff

Decision Tree for Optimization Software
guide
online courtesy of NSF and of professors Hans D.
Mittelmann and Peter Spellucci.

Steve Tate's
papers
on

Online and Dynamic Algorithms

Parallel Algorithms and Circuit Complexity

Robotics

Molecular Dynamics, Algebraic Algorithms, and
Geometry

Data Compression

Miscellaneous

"Designing Proxies for Stock Market
Indices is Computationally Hard"

"Arithmetic Circuit Complexity and
Motion Planning", PhD Thesis

"Report on the Workshop on Data and
Image Compression Needs and Uses in the
Scientific Community"

Tabu Search
A metastrategy for guiding search heuristics away from
quickly revisiting paths already visited.

Global Optimization Survey: Tabu Search
Sandia Labs on Tabu Search, introduction and bibliography

Technical University at Braunschweig on Tabu Search
overview, pseudocode, clear explaination, and bibliography

Tabu Search
From: Frequency Assignment Algorithms,
Radiocommunications Agency Agreement, Ref. RCCM
070, Interim Report

Tony White on Tabu Search
this Carleton University researcher gives a
definition plus links to books, working groups,
researchers, and original source publications

A Tabu Search Bibliography

Tabu Search

The Traveling Salesman Problem
My personal programming obsession.

A Traveling Salesman Problem Length
Estimator
for the case of random points in a Euclidian N
Cube, part of a larger article, in PDF.

Traveling Salesman Problem  Home Page
"Car 54 Contest"
banner is most identifying feature, by the authors
of Concorde.

The
CONCORDE
Traveling Salesman Problem source code library,
for problems of sizes up to say a million
waypoints.

Web page at Rutgers of Professor Vasek Chvatal, with lots of
links
for good stuff, in particular
Graph Theory
(perfect graphs),
the
Traveling Salesman Problem,
and more.

Torsten Reil's genetic algorithm Traveling Salesman
Java applet is not quite the classical problem, it has
a start and an end point instead of a circuit (but
they can be put atop one another to achieve the same
result as the usual TSP), and it doesn't find
"optimum" solutions, but it finds a
nonselfintersecting solution for hundreds of cites
in seconds, and survives working problems with at
least a couple of thousand cites, which is not too
shabby at all. The algorithm is very simple, a
ratcheting mutation algorithm, without the crossover
complexities of a standard genetic algorithm, but very
effective nevertheless.
Torsten has moved on from school to run a company, so
his Oxford address where this applet was originally
found no longer works, but he was kind enough to send
me a copy of the applet java executable classes and
HTML wrapper so that others may download
this zip file
and try his example code on their own Jave runtime
equipped machines.
The same code doesn't work for me from my own web
site, but does work when I download it, and I'm too
lazy to figure out why, thus the zip file.

Traveling Salesman
Problem
 in German  Simulated Annealing and Neural
Net, plus demos. This is part of an excellent
larger library of theory and demos about math
stuff (various sorts, string
matching, graph theory, Fast Fourier Transform,
and NPComplete Problems) maintained by
professor Hans Werner Lang. It is enough to
make me brush the rust off my German!

Traveling Salesman Problem  a brief
description
only, from
Martin Sewell.

Scott Robert Ladd at Coyote Gulch Productions presents
Traveler
(except that he spells it with the less
preferred spelling)  a fairly fast (for small
problems) blind traveling salesman Java demo.

A Fast TSP
Solver
using a Genetic Algorithm, on the pages of professor
Diane J. Cook
of the University of Texas at Arlington.
The original, by Hiroaki Sengoki, is also available via Hitachi, Ltd.,
here.

Splendid, little known fast heuristic, a blend of asexual and
sexual GA methods, the
"Inverover
Operator for the TSP" by Guo Tau and Zbigniew
Michalewicz

Connie Ramsey at NRL's Navy Center for Applied
Research in Artificial Intelligence
shows
the results for a fixed problem application of
a Genetic Algorithm to the TSP.

TSP overview
report

Comparison of various approaches to solving
Traveling Salesman Problem
by Basu Vaidyanathan at the University of
Texas, gives pseudocode for several important
TSP solution techniques. Yum!

Genetic Algorithms with
Memory
for Traveling Salesman Problems
by Sushil J. Louis and Gong Li  Dept. of
Computer Science, University of Nevada

Elastic Net Method for TSP

Mark H. Noschang, The TSP: Review of theory and current research,
SALESMAN
This page has gone missing, which is a
shame, it is referenced from all over the
net. If you find a new location for it,
please let me know.

O. Martin and Steve W. Otto,
Combining Simulated Annealing with Local Search Heuristics

TSPLIB
Gerhard Reinelt's
Sample Instances of TSP
in a test case library for the TSP

Professor Pablo Moscato's home
page,
wherein lie the Traveling Salesman Problem
TSPBIB
bibliographic database and the
Fractal
Instances of the Traveling Salesman Problem
pages (including many links to LSystems
tutorials), among other wonderful things. This
site can be extremely slow to come up at
times.

Traveling Salesman
Constants by Steven Finch,
part of the MathSoft pages.

Discrete
 Optimization with discrete variables, including links to some TSP code.
This page, maintained by
Kent Paul Dolan
xanthian@well.com
,
was last updated
20070103.