Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 4, pp. 481-507. 
@article{RO_1999__33_4_481_0,
     author = {Demange, Marc and Paschos, Vangelis Th.},
     title = {Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {481--507},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {4},
     year = {1999},
     mrnumber = {1735449},
     zbl = {0961.90084},
     language = {en},
     url = {http://www.numdam.org/item/RO_1999__33_4_481_0/}
}
TY  - JOUR
AU  - Demange, Marc
AU  - Paschos, Vangelis Th.
TI  - Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1999
SP  - 481
EP  - 507
VL  - 33
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1999__33_4_481_0/
LA  - en
ID  - RO_1999__33_4_481_0
ER  - 
%0 Journal Article
%A Demange, Marc
%A Paschos, Vangelis Th.
%T Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1999
%P 481-507
%V 33
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1999__33_4_481_0/
%G en
%F RO_1999__33_4_481_0
Demange, Marc; Paschos, Vangelis Th. Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 4, pp. 481-507. http://www.numdam.org/item/RO_1999__33_4_481_0/

1. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, in Proc. FOCS'92, 1992, p. 14-23. | Zbl

2. G. Ausiello, A. D'Atri and M. Protasi, Structure preserving reductions among convex optimization problems, J. Comput. System Sci., 1980, 21, p. 136-153. | MR | Zbl

3. C. Berge, Graphs and hypergraphs, North Holland, Amsterdam, 1973. | MR | Zbl

4. M. Demange, P. Grisoni, V. T. Paschos, Approximation results for the minimum graph coloring problem, Inform. Process. Lett., 1994, 50, p. 19-23. | MR | Zbl

5. M. Demange and V. T. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoret. Comput. Sci., 1996, 158, p. 117-141. | MR | Zbl

6. M. Demange and V. T. Paschos, Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale, Math. Inf. Sci. Humaines, 1996, 735, p. 51-66. | Numdam | MR | Zbl

7. W. Fernandez-De La Vega and G. S. Lueker, Bin packing can be solved within 1 + Є in linear time, Combinatorica, 1981, 1, n° 4, p. 349-355. | MR | Zbl

8. M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, Ed., San Francisco, 1979. | MR | Zbl

9. M. M. Halldórsson, Approximating k-set cover and complementary graph coloring, in Proc. International Integer Programming and Combinatorial Optimization Conference, Springer Verlag, Lecture Notes in Computer Science, 1996, 1084, p. 118-131. | MR

10. R. Hassin and S. Lahav, Maximizing the number of unused colors in the vertex coloring problem, Inform. Process. Lett., 1994, 52, p. 87-90. | MR | Zbl

11. D. S. Johnson, Fast algorithms for bin packing, J. Comput. System Sci., 1974, 8, p. 272-314. | MR | Zbl

12. D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey and R. L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 1974, 3, n° 4, p. 298-325. | MR | Zbl

13. A. Paz and S. Moran, Non deterministic polynomial optimization problems and their approximations, Theoret. Comput. Sci., 1981, 75, p. 251-277. | MR | Zbl

14. H. U. Simon, On approximate solutions for combinatorial optimization problems, SIAM J. Disc. Math., 1990, 3, n° 2, p. 294-310. | MR | Zbl