Recherche et téléchargement d’archives de revues mathématiques numérisées

 
 
  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

Bibliographie

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 2014 | Crédit | Plan du site