Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
Marc Demange; Vangelis Paschos
RAIRO - Operations Research (2010)
- Volume: 36, Issue: 3, page 237-277
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- S. Arora, C. Lund, R. Motwani, M. Sudan et M. Szegedy, Proof verification and intractability of approximation problems, in Proc. FOCS'92 (1992) 14-23.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela et M. Protasi, Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Heildelberg (1999).
- C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973).
- P. Berman et M. Fürer, Approximating maximum independent set in bounded degree graphs, in Proc. Symposium on Discrete Algorithms (1994) 365-371.
- B.B. Boppana et M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs. BIT32 (1992) 180-196.
- V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res.4 (1979) 233-235.
- S.A. Cook, The complexity of theorem-proving procedures, in Proc. STOC'71 (1971) 151-158.
- M. Demange, P. Grisoni et V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci.209 (1998) 107-122.
- M. Demange, J. Monnot et V.T. Paschos, Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett.12 (1999) 127-133.
- height 2pt depth -1.6pt width 23pt, Maximizing the number of unused bins. Found. Comput. Decision Sci.26 (2001) 169-186.
- M. Demange et V.T. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci.158 (1996) 117-141.
- height 2pt depth -1.6pt width 23pt, Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines135 (1996) 51-66.
- height 2pt depth -1.6pt width 23pt, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances. RAIRO: Oper. Res. (à paraître).
- height 2pt depth -1.6pt width 23pt, Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett.10 (1997) 105-110.
- height 2pt depth -1.6pt width 23pt, Towards a general formal framework for polynomial approximation. LAMSADE, Université Paris-Dauphine, Cahier du LAMSADE177 (2001).
- R. Duh et M. Fürer, Approximation of k-set cover by semi-local optimization, in Proc. STOC'97 (1997) 256-265.
- U. Feige et J. Kilian, Zero knowledge and the chromatic number, in Proc. Conference on Computational Complexity (1996) 278-287.
- W. Fernandez de la Vega, Sur la cardinalité maximum des couplages d'hypergraphes aléatoires uniformes. Discrete Math.40 (1982) 315-318.
- M.R. Garey et D.S. Johnson, Computers and intractability. A guide sto the theory of NP-completeness. W.H. Freeman, San Francisco (1979).
- M.M. Halldórsson, A still better performance guarantee for approximate graph coloring. Inform. Process. Lett.45 (1993) 19-23.
- height 2pt depth -1.6pt width 23pt, Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995).
- height 2pt depth -1.6pt width 23pt, Approximating k-set cover and complementary graph coloring, in Proc. International Integer Programming and Combinatorial Optimization Conference. Springer Verlag, Lecture Notes in Comput. Sci.1084 (1996) 118-131.
- M.M. Halldórsson et J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, in Proc. STOC'94 (1994) 439-448.
- height 2pt depth -1.6pt width 23pt, Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic J. Comput.1 (1994) 475-492.
- R. Hassin et S. Lahav, Maximizing the number of unused colors in the vertex coloring problem. Inform. Process. Lett.52 (1994) 87-90.
- J. Håstad, Clique is hard to approximate within n1-ε. Acta Math.182 (1999) 105-142.
- D.S. Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math.6 (1983) 243-254.
- height 2pt depth -1.6pt width 23pt, Approximation algorithms for NP-hard problems. PWS, Boston (1997).
- O.H. Ibarra et C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. Assoc. Comput. Mach.22 (1975) 463-468.
- D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. System Sci.9 (1974) 256-278.
- R.M. Karp, Reducibility among combinatorial problems, dans Complexity of computer computations, édité par R.E. Miller et J.W. Thatcher. Plenum Press, New York (1972) 85-103.
- S. Khanna, R. Motwani, M. Sudan et U. Vazirani, On syntactic versus computational views of approximability. SIAM J. Comput.28 (1998) 164-191.
- H.R. Lewis et C.H. Papadimitriou, Elements of the theory of computation. Prentice-Hall (1981).
- C. Lund et M. Yannakakis, On the hardness of approximating minimization problems. J. Assoc. Comput. Mach.41 (1994) 960-981.
- R. Motwani, Lecture notes on approximation algorithms, Vol. I. Stanford University (1993).
- G.L. Nemhauser, L.A. Wolsey et M.L. Fischer, An analysis of approximations for maximizing submodular set functions. Math. Programming14 (1978) 265-294.
- C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981).
- R. Raz et S. Safra, A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP, in Proc. STOC'97 (1997) 475-484.
- D. Simchi-Levi, New worst-case results for the bin-packing problem. Naval Res. Logistics41 (1994) 579-585.
- P. Turán, On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok48 (1941) 436-452.
- V. Vazirani, Approximation algorithms. Springer, Heildelberg (2001).