Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems

Marc Demange; Vangelis Th. Paschos

RAIRO - Operations Research - Recherche Opérationnelle (1999)

  • Volume: 33, Issue: 4, page 481-507
  • ISSN: 0399-0559

How to cite

top

Demange, Marc, and Paschos, Vangelis Th.. "Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems." RAIRO - Operations Research - Recherche Opérationnelle 33.4 (1999): 481-507. <http://eudml.org/doc/105201>.

@article{Demange1999,
author = {Demange, Marc, Paschos, Vangelis Th.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {NP-complete problem; complexity; polynomial time approximation algorithm; bin packing; coloring; covering},
language = {eng},
number = {4},
pages = {481-507},
publisher = {EDP-Sciences},
title = {Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems},
url = {http://eudml.org/doc/105201},
volume = {33},
year = {1999},
}

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
PB - EDP-Sciences
VL - 33
IS - 4
SP - 481
EP - 507
LA - eng
KW - NP-complete problem; complexity; polynomial time approximation algorithm; bin packing; coloring; covering
UR - http://eudml.org/doc/105201
ER -

References

top
  1. 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. Zbl0977.68539
  2. 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. Zbl0441.68049MR589808
  3. 3. C. BERGE, Graphs and hypergraphs, North Holland, Amsterdam, 1973. Zbl0254.05101MR357172
  4. 4. M. DEMANGE, P. GRISONI, V. T. PASCHOS, Approximation results for the minimum graph coloring problem, Inform. Process. Lett., 1994, 50, p. 19-23. Zbl0806.68085MR1279492
  5. 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. Zbl0871.90069MR1388966
  6. 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. Zbl0885.90093MR1435452
  7. 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. Zbl0485.68057MR647985
  8. 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. Zbl0411.68039MR519066
  9. 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. MR1441796
  10. 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. Zbl0809.05047MR1299662
  11. 11. D. S. JOHNSON, Fast algorithms for bin packing, J. Comput. System Sci., 1974, 8, p. 272-314. Zbl0284.68023MR373370
  12. 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. Zbl0297.68028MR434396
  13. 13. A. PAZ and S. MORAN, Non deterministic polynomial optimization problems and their approximations, Theoret. Comput. Sci., 1981, 75, p. 251-277. Zbl0459.68015MR632398
  14. 14. H. U. SIMON, On approximate solutions for combinatorial optimization problems, SIAM J. Disc. Math., 1990, 3, n° 2, p. 294-310. Zbl0699.68077MR1039300

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.