A. Aiello, E. Burattini, M. Furnari, A. Massarotti, and F. Ventriglia, Computational complexity: the problem of approximation, In: Algebra, Combinatorics and Logic in Computer Science, vol.42, pp.51-62, 1983.

A. Aiello, E. Burattini, A. Massarotti, and F. Ventriglia, A new evaluation function for approximation algorithms, Proceedings of Informatica 77, pp.1-4, 1977.

A. Aiello, E. Burattini, A. Massarotti, and F. Ventriglia, Towards a general principle of evaluation for approximate algorithms, RAIRO. Informatique th??orique, vol.13, issue.3, pp.227-239, 1979.
DOI : 10.1051/ita/1979130302271

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-spaccamela et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1999.
DOI : 10.1007/978-3-642-58412-1

G. Ausiello, A. D. Atri, and M. Protasi, Structure preserving reductions among convex optimization problems, Journal of Computer and System Sciences, vol.21, issue.1, pp.136-153, 1980.
DOI : 10.1016/0022-0000(80)90046-X
URL : http://doi.org/10.1016/0022-0000(80)90046-x

G. J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM, vol.22, issue.3, pp.329-340, 1975.
DOI : 10.1145/321892.321894

G. J. Chaitin, A. Arslanov, and C. S. Calude, Program-size complexity computes the halting problem, EATCS Bulletin, vol.57, pp.198-200, 1995.

G. Cornuejols, M. L. Fisher, and G. L. Nemhauser, Exceptional Paper???Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms, Management Science, vol.23, issue.8, pp.789-810, 1977.
DOI : 10.1287/mnsc.23.8.789

M. Demange, P. Grisoni, V. Th, and . Paschos, Approximation results for the minimum graph coloring problem, Information Processing Letters, vol.50, issue.1, pp.19-23, 1994.
DOI : 10.1016/0020-0190(94)90039-6

M. Demange, P. Grisoni, V. Th, and . Paschos, Differential approximation algorithms for some combinatorial optimization problems, Theoretical Computer Science, vol.209, issue.1-2, pp.107-122, 1998.
DOI : 10.1016/S0304-3975(97)00099-6

M. Demange, V. Th, and . Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoretical Computer Science, vol.158, issue.1-2, pp.117-141, 1996.
DOI : 10.1016/0304-3975(95)00060-7

M. M. Halldórsson, Approximating discrete collections via local improvements, Proc. 6th ACM- SIAM Symp. on Discrete Algorithms, pp.160-169, 1995.

M. M. Halldórsson, Approximating k-set cover and complementary graph coloring, Integer Programming and Combinatorial Optimization: Proc. 5th Internat. IPCO Conf. Lecture Notes in Computer Science 1084, pp.118-131, 1996.
DOI : 10.1007/3-540-61310-2_10

R. Hassin and S. Khuller, z-Approximations, Journal of Algorithms, vol.41, issue.2, pp.429-442, 2001.
DOI : 10.1006/jagm.2001.1187

R. Hassin and S. Lahav, Maximizing the number of unused colors in the vertex coloring problem, Information Processing Letters, vol.52, issue.2, pp.87-90, 1994.
DOI : 10.1016/0020-0190(94)00113-8

J. E. Hopcroft and R. M. Karp, An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing, vol.2, issue.4, pp.225-231, 1973.
DOI : 10.1137/0202019

J. Hromkovi?, Algorithms for Hard Problems, 2001.

S. Irani and A. R. Karlin, Online computation Approximation Algorithms for NP-hard Problems, pp.521-564, 1996.

D. S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.256-278, 1974.
DOI : 10.1145/800125.804034

L. A. Levin, Universal sequential search problems Russian original: Problemy Peredachi Informatsii, Problems Inform. Transmission, vol.9, issue.9, pp.265-266115, 1973.

M. Li and P. M. Vitányi, An Introduction to Kolmogorov Complexity and its Applications, 1997.

L. Lovász and M. D. Plummer, Matching Theory, North-Holland Mathematics Studies 121, Ann. Discrete Math, vol.29, 1986.

D. W. Matula, G. Marble, and J. D. Isaacson, Graph coloring algorithms, Graph Theory and Computing, pp.109-122, 1972.

S. Micali and V. V. Vazirani, An O( |V | |E|) algorithm for finding maximum matching in general graphs, Proc. 21st Ann, pp.17-27, 1980.

J. Rissanen, A Universal Prior for Integers and Estimation by Minimum Description Length, The Annals of Statistics, vol.11, issue.2, pp.416-431, 1983.
DOI : 10.1214/aos/1176346150

W. Tzeng and G. King, Three-quarter approximation for the number of unused colors in graph coloring, Information Sciences, vol.114, issue.1-4, pp.105-126, 1999.
DOI : 10.1016/S0020-0255(98)10058-0