This is the Practical Approximation Algorithms Library.

Contents

The library consists of several sublibraries

• Algorithms
  • Local Search
    • 2-opt for Traveling Salesman Problem
    • Facility Location
    • K-Median
    • Capacitated Facility Location
  • Iterative Rounding
    • Bounded-Degree Minimum Spanning Tree
    • Generalised Assignment
    • Steiner Network
    • Tree Augmentation
    • Steiner Tree 1.39 Approximation
  • Greedy
    • Budgeted Maximum Coverage
    • Maximum Coverage
    • K-center
    • Minimum K-Cut
    • Knapsack Greedy
    • Shortest Superstring
    • Scheduling Jobs
    • Scheduling Jobs on Identical Parallel Machines
    • Scheduling Jobs with Deadlines on a Single Machine
    • Steiner Tree Greedy
    • Set Cover
  • Dynamic
    • Knapsack Dynamic
    • Knapsack 0/1 FPTAS
  • Exact
    • Steiner Tree Dreyfus Wagner
  • Linear Programming
    • Multiway Cut
  • Combinatorial Auctions
    • Winner Determination in MUCA
    • Fractional Winner Determination in MUCA
  • Regression
    • Locality-sensitive hashing nearest neighbors regression
  • Miscellaneous
    • Steiner Tree 11/6 Approximation
  • Clustering
    • k-means clustering engine
    • k-means clustering
  • Sketch
    • Frequent-directions
• Concepts
  • Metric
  • Cycle
  • Voronoi
• Data Structures
  • Components
  • 2k-1 Approximate Vertex-Vertex Distance Oracle
  • paal::data_structures::stack
  • paal::data_structures::graph_metric
  • paal::data_structures::array_metric
  • paal::data_structures::euclidean_metric
  • paal::data_structures::simple_cycle
  • paal::data_structures::splay_cycle
  • paal::data_structures::object_with_copy
  • paal::data_structures::facility_location_solution
  • paal::data_structures::voronoi
  • paal::data_structures::capacitated_voronoi
  • paal::data_structures::subsets_iterator
  • paal::data_structures::vertex_to_edge_iterator

  • paal::data_structures::bimap