<p>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.</p>

CC BY-SA 3.0
2013-02-16T15:41:22.040Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-02-17T23:14:06.447Z
I implemented a few approximation algorithms for [NetworkX](http://networkx.github.com/documentation/latest/reference/algorithms.approximation.html). They were usually methods that were simple to understand and code, and not necessarily the most up-to-date.
Nicholas Mancuso
CC BY-SA 3.0
2013-02-20T08:29:01.577Z
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.
Neal Young
<reference-request><approximation-algorithms><optimization>
Benchmarks for approximation algorithms
Mike Izbicki
# Benchmarks for approximation algorithms

(Asked by: username_0 on 2013-02-16)

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.

**Tags:** reference-request, approximation-algorithms, optimization
> **Comments:**
> **username_1**: 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.  
> **username_2**: I implemented a few approximation algorithms for [NetworkX](http://networkx.github.com/documentation/latest/reference/algorithms.approximation.html). They were usually methods that were simple to understand and code, and not necessarily the most up-to-date.  
> **username_3**: 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.  

---

## 0 answers

