Approximation algorithms

Polynomial-time algorithms with proved approximation ratios for NP-hard optimization: vertex cover, set cover, metric TSP, list scheduling, maximum coverage.

• Double-tree approximation for metric TSP
• Greedy set cover
• List scheduling on identical machines
• Maximum n-times coverage
• Vertex cover 2-approximation
• Weighted vertex cover by the pricing method

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.