Computational Complexity

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 NP-Completeness 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 NP-Completeness Page A mirror site of the one above.
SAT01 Notes Stas focuses on the satisfiability problem.
Stas Busygin's NP-Completeness 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
e82-a_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
- On-line 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 non-self-intersecting 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 NP-Complete 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 "Inver-over 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 L-Systems 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.