Differential approximation of NP-hard problems with equal size feasible solutions
RAIRO - Operations Research (2010)
- Volume: 36, Issue: 4, page 279-297
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- A. Aggarwal, H. Imai, N. Katoh and S. Suri, Finding k points with minimum diameter and related problems. J. Algorithms12 (1991) 38-56.
- A. Aiello, E. Burattini, M. Massarotti and F. Ventriglia, A new evaluation function for approximation. Sem. IRIA (1977).
- L. Alfandari and V.Th. Paschos, Approximating the minimum rooted spanning tree with depth two. Int. Trans. Oper. Res.6 (1999) 607-622.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela and M. Protasi, Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Verlag (1999).
- G. Ausiello, P. Crescenzi and M. Protasi, Approximate solutions of NP-optimization problems. Theoret. Comput. Sci.150 (1995) 1-55.
- G. Ausiello, A. D'Atri and M. Protasi, Structure preserving reductions among convex optimization problems. J. Comput. System Sci.21 (1980) 136-153.
- N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 338 Grad School of Indistrial Administration, CMU (1976).
- G. Cornuejols, M.L. Fisher and G.L. Memhauser, Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci.23 (1977) 789-810.
- P. Crescenzi and V. Kann, A compendium of NP-optimization problems. Available on www address: http://www.nada.kth.se/ viggo/problemlist/compendium.html (1998).
- P. Crescenzi and A. Panconesi, Completness in approximation classes. Inform. and Comput.93 (1991) 241-262.
- M. Demange, D. de Werra and J. Monnot, Weighted node coloring: When stable sets are expensive (extended abstract), in Proc. WG 02. Springer Verlag, Lecture Notes in Comput. Sci. 2573 (2002) 114-125.
- M. Demange, P. Grisoni and V.Th. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci.209 (1998) 107-122.
- M. Demange, J. Monnot and V.Th. Paschos, Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett.12 (1999) 127-133.
- M. Demange, J. Monnot and V.Th. Paschos, Differential approximation results for the Steiner tree problem. Appl. Math. Lett. (to appear).
- M. Demange and V.Th. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci.156 (1996)117-141.
- H.A. Eiselt, M. Gendreau and G. Laporte, Arc routing problems, part II: The rural postman problem. Oper. Res. (Survey, Expository and Tutorial)43 (1995) 399-414.
- L. Engebretsen and M. Karpinski, Approximation hardness of TSP with bounded metrics. Available on www address: http://www.nada.kth.se/ enge/enge.bib (2002). ECCC Report TR00-089 (2000).
- M.L. Fisher, G.L. Nemhauser and L.A. Wolsey, An analysis of approximations for finding a maximum weight hamiltonian circuit. Oper. Res.27 (1979) 799-809.
- G.N. Frederickson, Approximation algorithm for some postman problems. J. ACM26 (1979) 538-554.
- M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. CA. Freeman (1979).
- N. Garg, A 3-approximation for the minimum tree spanning k vertices. In Proc. FOCS (1996) 302-309.
- L. Gouveia, Multicommodity flow models for spanning tree with hop constraints. Eur. J. Oper. Res.95 (1996) 178-190.
- L. Gouveia, Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. J. Comput.10 (1998) 180-188.
- L. Gouveia and E. Janssen, Designing reliable tree with two cable technologies. Eur. J. Oper. Res.105 (1998) 552-568.
- N. Guttmann-Beck, R. Hassin, S. Khuller and B. Raghavachari, Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica4 (2000) 422-437.
- M.M. Halldorsson, K. Iwano, N. Katoh and T. Tokuyama, Finding subsets maximizing minimum structures, in Proc. SODA (1995) 150-159.
- R. Hassin and S. Khuller, z-approximations. J. Algorithms41 (2002) 429-442.
- R. Hassin and S. Rubinstein, An approximation algorithm for maximum packing of 3-edge paths. Inform. Process. Lett.6 (1997) 63-67.
- D. Hochbaum, Approximation algorithms for NP-hard problems. P.W.S (1997).
- J.A. Hoogeveen, Analysis of christofides' heuristic: Some paths are more difficult than cycles. Oper. Res. Lett.10 (1991) 291-295.
- D.S. Johnson and C.H. Papadimitriou, Performance guarantees for heuristics, edited by E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, The Traveling Salesman Problem: A guided tour of Combinatorial Optimization. Wiley, Chichester (1985) 145-180.
- R.M. Karp, Reducibility among combinatorial problems, edited by R.E Miller and J.W. Thatcher, Complexity of Computer Computations. Plenum Press, NY (1972) 85-103.
- D.G. Kirkpatrick and P. Hell, The complexity of a generalized matching problem, in Proc. STOC (1978) 240-245.
- G. Kortsarz and D. Peleg, Approximating shallow-light trees, in Proc. SODA (1997) 103-110.
- S.R. Kosaraju, J.K. Park and C. Stein, Long tours and short superstrings, in Proc. FOCS (1994) 166-177.
- T. Magnanti and L. Wolsey, Optimal trees, Network models. North-Holland, Handbooks Oper. Res. Management Sci.7 (1995) 503-615.
- P. Manyem and M.F.M. Stallmann, Some approximation results in multicasting, Working Paper. North Carolina State University (1996).
- J.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: Part II - A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput.28 (1999) 1298-1309.
- J. Monnot, Families of critical instances and polynomial approximation, Ph.D. Thesis. LAMSADE, Université Paris IX, Dauphine (1998) (in French).
- J. Monnot, The maximum f-depth spanning tree problem. Inform. Process. Lett.80 (2001) 179-187.
- J. Monnot, V.Th. Paschos and S. Toulouse, Differential approximation results for traveling salesman problem with distance 1 and 2 (extended abstract). Proc. FCT2138 (2001) 275-286.
- J. Monnot, V.Th. Paschos and S. Toulouse, Approximation polynomiale des problèmes NP-difficiles: optima locaux et rapport différentiel. Édition HERMÈS Science Lavoisier (2003).
- J.S. Naor and B. Schieber, Improved approximations for shallow-light spanning trees, in Proc. FOCS (1997) 536-541.
- C.S. Orloff, A fundamental problem in vehicle routing. Networks4 (1974) 35-64.
- P. Orponen and H. Mannila, On approximation preserving reductions: Complete problems and robust measures, Technical Report C-1987-28. Department of Computer Science, University of Helsinki (1987).
- R. Ravi, R. Sundaram, M.V. Marathe, D.J. Rosenkrants and S.S. Ravi, Spanning tree short or small. SIAM J. Discrete Math.9 (1996) 178-200.
- S. Sahni and T. Gonzalez, P-complete approximation problems. J. ACM23 (1976) 555-565.
- S.A. Vavasis, Approximation algorithms for indefinite quadratic programming. Math. Programming57 (1972) 279-311.
- E. Zemel, Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res.6 (1981) 319-332.