Differential approximation of NP-hard problems with equal size feasible solutions
RAIRO - Operations Research - Recherche Opérationnelle (2002)
- Volume: 36, Issue: 4, page 279-297
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- [1] A. Aggarwal, H. Imai, N. Katoh and S. Suri, Finding points with minimum diameter and related problems. J. Algorithms 12 (1991) 38-56. Zbl0715.68082MR1088115
- [2] A. Aiello, E. Burattini, M. Massarotti and F. Ventriglia, A new evaluation function for approximation. Sem. IRIA (1977). Zbl0604.68047
- [3] L. Alfandari and V.Th. Paschos, Approximating the minimum rooted spanning tree with depth two. Int. Trans. Oper. Res. 6 (1999) 607-622. MR1724458
- [4] 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). Zbl0937.68002MR1734026
- [5] G. Ausiello, P. Crescenzi and M. Protasi, Approximate solutions of NP-optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. Zbl0874.68145MR1357119
- [6] G. Ausiello, A. D’Atri and M. Protasi, Structure preserving reductions among convex optimization problems. J. Comput. System Sci. 21 (1980) 136-153. Zbl0441.68049
- [7] N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 338 Grad School of Indistrial Administration, CMU (1976).
- [8] 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. Zbl0361.90034MR444049
- [9] 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).
- [10] P. Crescenzi and A. Panconesi, Completness in approximation classes. Inform. and Comput. 93 (1991) 241-262. Zbl0734.68039MR1115527
- [11] 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. Zbl1022.68092MR2063804
- [12] M. Demange, P. Grisoni and V.Th. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. Zbl0912.68061MR1647498
- [13] 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. Zbl0942.68144MR1750071
- [14] M. Demange, J. Monnot and V.Th. Paschos, Differential approximation results for the Steiner tree problem. Appl. Math. Lett. (to appear). Zbl1046.90096MR1986043
- [15] 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. Zbl0871.90069MR1388966
- [16] 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. Zbl0853.90042MR1327413
- [17] 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). Zbl0986.90082MR2065863
- [18] 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. Zbl0412.90070MR542983
- [19] G.N. Frederickson, Approximation algorithm for some postman problems. J. ACM 26 (1979) 538-554. Zbl0405.90076MR535270
- [20] M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. CA. Freeman (1979). Zbl0411.68039MR519066
- [21] N. Garg, A -approximation for the minimum tree spanning vertices. In Proc. FOCS (1996) 302-309. MR1450628
- [22] L. Gouveia, Multicommodity flow models for spanning tree with hop constraints. Eur. J. Oper. Res. 95 (1996) 178-190. Zbl0947.90513
- [23] L. Gouveia, Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. J. Comput. 10 (1998) 180-188. Zbl1054.90622MR1637563
- [24] L. Gouveia and E. Janssen, Designing reliable tree with two cable technologies. Eur. J. Oper. Res. 105 (1998) 552-568. Zbl0955.90009
- [25] N. Guttmann–Beck, R. Hassin, S. Khuller and B. Raghavachari, Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 4 (2000) 422-437. Zbl0963.68226
- [26] M.M. Halldorsson, K. Iwano, N. Katoh and T. Tokuyama, Finding subsets maximizing minimum structures, in Proc. SODA (1995) 150-159. Zbl0848.68071MR1321846
- [27] R. Hassin and S. Khuller, -approximations. J. Algorithms 41 (2002) 429-442. Zbl1014.68222MR1869261
- [28] R. Hassin and S. Rubinstein, An approximation algorithm for maximum packing of 3-edge paths. Inform. Process. Lett. 6 (1997) 63-67. Zbl06585443MR1474580
- [29] D. Hochbaum, Approximation algorithms for NP-hard problems. P.W.S (1997). Zbl05899342
- [30] J.A. Hoogeveen, Analysis of christofides’ heuristic: Some paths are more difficult than cycles. Oper. Res. Lett. 10 (1991) 291-295. Zbl0748.90071
- [31] 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. Zbl0574.90086MR811472
- [32] 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. MR378476
- [33] D.G. Kirkpatrick and P. Hell, The complexity of a generalized matching problem, in Proc. STOC (1978) 240-245. Zbl1282.68182MR521059
- [34] G. Kortsarz and D. Peleg, Approximating shallow-light trees, in Proc. SODA (1997) 103-110. MR1447655
- [35] S.R. Kosaraju, J.K. Park and C. Stein, Long tours and short superstrings, in Proc. FOCS (1994) 166-177.
- [36] T. Magnanti and L. Wolsey, Optimal trees, Network models. North-Holland, Handbooks Oper. Res. Management Sci. 7 (1995) 503-615. Zbl0839.90135MR1420874
- [37] P. Manyem and M.F.M. Stallmann, Some approximation results in multicasting, Working Paper. North Carolina State University (1996).
- [38] J.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: Part II – A simple polynomial-time approximation scheme for geometric TSP, -MST, and related problems. SIAM J. Comput. 28 (1999) 1298-1309. Zbl0940.68062
- [39] J. Monnot, Families of critical instances and polynomial approximation, Ph.D. Thesis. LAMSADE, Université Paris IX, Dauphine (1998) (in French).
- [40] J. Monnot, The maximum -depth spanning tree problem. Inform. Process. Lett. 80 (2001) 179-187. Zbl1032.68087MR1859339
- [41] J. Monnot, V.Th. Paschos and S. Toulouse, Differential approximation results for traveling salesman problem with distance and (extended abstract). Proc. FCT 2138 (2001) 275-286. Zbl1003.90035MR1914277
- [42] 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). Zbl1140.90011
- [43] J.S. Naor and B. Schieber, Improved approximations for shallow-light spanning trees, in Proc. FOCS (1997) 536-541.
- [44] C.S. Orloff, A fundamental problem in vehicle routing. Networks 4 (1974) 35-64. Zbl0368.90130MR332133
- [45] 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).
- [46] 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. Zbl0855.05058MR1386876
- [47] S. Sahni and T. Gonzalez, P-complete approximation problems. J. ACM 23 (1976) 555-565. Zbl0348.90152MR408313
- [48] S.A. Vavasis, Approximation algorithms for indefinite quadratic programming. Math. Programming 57 (1972) 279-311. Zbl0845.90095MR1195028
- [49] E. Zemel, Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res. 6 (1981) 319-332. Zbl0538.90065MR629633