I'm working on a Haskell library for approximation algorithms. In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others. Of course, I'd like to benchmark my library against other libraries in terms of both speed and the goodness of the solution. So, are there any good benchmarks for these problems out there? I'm looking for something like the UCI machine learning repository, but for approximation algorithms.

  • $\begingroup$ I've used various NP-complete problems as application studies in my algorithms class, and I've never found anything along the lines of what you're looking for. For specific problems you might find specific benchmarks though: for example, there are separate benchmarks/code for VC, TSP and coloring. $\endgroup$ – Suresh Venkat Feb 16 '13 at 15:41
  • $\begingroup$ I implemented a few approximation algorithms for NetworkX. They were usually methods that were simple to understand and code, and not necessarily the most up-to-date. $\endgroup$ – Nicholas Mancuso Feb 17 '13 at 23:14
  • $\begingroup$ You might take a look through the benchmarks from the old DIMACS implementation challenges. Also, I would look for integer linear programming benchmarks; many of those are for NP-hard problems. Look through work by David Applegate and others for libraries of TSP benchmarks. $\endgroup$ – Neal Young Feb 20 '13 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.