| |
Table des matières de ce fascicule | Article précédent | Article suivant
Demange, Marc; Paschos, Vangelis Th.
Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems. Revue française d'automatique, d'informatique et de recherche opérationnelle. Recherche opérationnelle, 33 no. 4 (1999), p. 481-507
Texte intégral djvu | pdf | Analyses MR 1735449 | Zbl 0961.90084
URL stable: http://www.numdam.org/item?id=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 0977.68539
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 589808 | Zbl 0441.68049
3. C. BERGE, Graphs and hypergraphs, North Holland, Amsterdam, 1973. MR 357172 | Zbl 0254.05101
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 1279492 | Zbl 0806.68085
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 1388966 | Zbl 0871.90069
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 1435452 | Zbl 0885.90093
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 647985 | Zbl 0485.68057
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 519066 | Zbl 0411.68039
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 1441796
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 1299662 | Zbl 0809.05047
11. D. S. JOHNSON, Fast algorithms for bin packing, J. Comput. System Sci., 1974, 8, p. 272-314. MR 373370 | Zbl 0284.68023
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 434396 | Zbl 0297.68028
13. A. PAZ and S. MORAN, Non deterministic polynomial optimization problems and their approximations, Theoret. Comput. Sci., 1981, 75, p. 251-277. MR 632398 | Zbl 0459.68015
14. H. U. SIMON, On approximate solutions for combinatorial optimization problems, SIAM J. Disc. Math., 1990, 3, n° 2, p. 294-310. MR 1039300 | Zbl 0699.68077
|
|
Copyright Cellule MathDoc 2013 | Crédit | Plan du site
|
