File Approximation.h

↰ Parent directory (ADS/intractable)

The approximation algorithms of section 19.2 and of the exercises 19.6 and 19.8.

Definition (ADS/intractable/Approximation.h)

Detailed Description

An absolute approximation gives a feasible x’ with :math:` | c( x’ ) - c( x^* ) | / | c( x^* ) | leq e , e a constant of the algorithm; an :math: epsilon -approximation takes :math: epsilon ` in input, in a time polynomial in the size and in general exponential in :math:` 1 / epsilon `.

  • firstFit(), ff and, on the volumes in decreasing order, ffd for BIN PACKING: no two boxes are filled at most half, so that N < 2 N*;

  • deltaTsp() for the salesman with the triangle inequality: the nodes of a minimum spanning tree in preorder, the tree walked twice with the cities already visited skipped, at most twice the optimum (the bound is reached by the two concentric polygons of Figura 19.3);

  • tspGap(): the distances of Teorema 19.2, 1 on the edges of G and s n elsewhere, so that an approximation within s would decide CIRCUITO HAMILTONIANO;

  • apSubsetSum(), the :math:` epsilon -approximation of the optimization SOMMA DI SOTTOINSIEME with :math: epsilon = 1 / ( h + 1 ) : each set of at most h elements, completed greedily on the elements in decreasing order, :math: O( h n^{h+1} ) `;

  • vertexCoverApprox(), the two ends of each edge not yet covered, a matching whose ends are at most twice a minimum cover (exercise 19.6);

  • knapsackApprox(), an :math:` epsilon -approximation of ZAINO in time polynomial in n and :math: 1 / epsilon ` (exercise 19.8): the profits divided by :math:` K = epsilon p_{max} / n ` and rounded down, and the least volume of each rounded profit by dynamic programming, at least :math:` ( 1 - epsilon ) ` times the optimum in :math:` O( n^3 / epsilon ) `.

The contracts [see File Contract.h]: the volumes, the profits and the sums are not negative, the distances square and symmetric, and the triangle inequality that the bound of deltaTsp() rests on is an audit, O( n^3 ); each solution returned is checked as feasible. The operations are defined in Approximation.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 19.2 and exercises 19.6, 19.8, https://algoritmicamente.it/materiali/libro/capitoli/cap19.pdf

    1. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing 3(4), 299-325, 1974, doi:10.1137/0203025

    1. Rosenkrantz, R. E. Stearns, P. M. Lewis, An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing 6(3), 563-581, 1977, doi:10.1137/0206041

    1. Ibarra, C. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems, Journal of the ACM 22(4), 463-468, 1975, doi:10.1145/321906.321909

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions