Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot

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

  • Volume: 36, Issue: 4, page 279-297
  • ISSN: 0399-0559

Abstract

top
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of π , as well as general minimization and minimization with triangular inequality versions of π . Then, we prove that some well known problems do belong to this class, such as special cases of both spanning tree and vehicles routing problems. In particular, we study the strict rural postman problem (called S R P P ) and show that both the maximization and the minimization versions can be approximately solved, in polynomial time, within a differential ratio bounded above by 1 / 2 . From these results, we derive new bounds for standard ratio when restricting edge weights to the interval [ a , t a ] (the S R P P [ t ] problem): we respectively provide a 2 / ( t + 1 ) - and a ( t + 1 ) / 2 t -standard approximation for the minimization and the maximization versions.

How to cite

top

Monnot, Jérôme. "Differential approximation of NP-hard problems with equal size feasible solutions." RAIRO - Operations Research - Recherche Opérationnelle 36.4 (2002): 279-297. <http://eudml.org/doc/245799>.

@article{Monnot2002,
abstract = {In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem $\pi $ which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of $\pi $, as well as general minimization and minimization with triangular inequality versions of $\pi $. Then, we prove that some well known problems do belong to this class, such as special cases of both spanning tree and vehicles routing problems. In particular, we study the strict rural postman problem (called $SRPP$) and show that both the maximization and the minimization versions can be approximately solved, in polynomial time, within a differential ratio bounded above by $1/2$. From these results, we derive new bounds for standard ratio when restricting edge weights to the interval $[a,ta]$ (the $SRPP[t]$ problem): we respectively provide a $2/(t+1)$- and a $(t+1)/2t$-standard approximation for the minimization and the maximization versions.},
author = {Monnot, Jérôme},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {approximate algorithms; differential ratio; performance ratio; analysis of algorithms; Approximate algorithms},
language = {eng},
number = {4},
pages = {279-297},
publisher = {EDP-Sciences},
title = {Differential approximation of NP-hard problems with equal size feasible solutions},
url = {http://eudml.org/doc/245799},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Monnot, Jérôme
TI - Differential approximation of NP-hard problems with equal size feasible solutions
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 4
SP - 279
EP - 297
AB - In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem $\pi $ which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of $\pi $, as well as general minimization and minimization with triangular inequality versions of $\pi $. Then, we prove that some well known problems do belong to this class, such as special cases of both spanning tree and vehicles routing problems. In particular, we study the strict rural postman problem (called $SRPP$) and show that both the maximization and the minimization versions can be approximately solved, in polynomial time, within a differential ratio bounded above by $1/2$. From these results, we derive new bounds for standard ratio when restricting edge weights to the interval $[a,ta]$ (the $SRPP[t]$ problem): we respectively provide a $2/(t+1)$- and a $(t+1)/2t$-standard approximation for the minimization and the maximization versions.
LA - eng
KW - approximate algorithms; differential ratio; performance ratio; analysis of algorithms; Approximate algorithms
UR - http://eudml.org/doc/245799
ER -

References

top
  1. [1] A. Aggarwal, H. Imai, N. Katoh and S. Suri, Finding k points with minimum diameter and related problems. J. Algorithms 12 (1991) 38-56. Zbl0715.68082MR1088115
  2. [2] A. Aiello, E. Burattini, M. Massarotti and F. Ventriglia, A new evaluation function for approximation. Sem. IRIA (1977). Zbl0604.68047
  3. [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. [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. [5] G. Ausiello, P. Crescenzi and M. Protasi, Approximate solutions of NP-optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. Zbl0874.68145MR1357119
  6. [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. [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. [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. [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. [10] P. Crescenzi and A. Panconesi, Completness in approximation classes. Inform. and Comput. 93 (1991) 241-262. Zbl0734.68039MR1115527
  11. [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. [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. [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. [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. [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. [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. [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. [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. [19] G.N. Frederickson, Approximation algorithm for some postman problems. J. ACM 26 (1979) 538-554. Zbl0405.90076MR535270
  20. [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. [21] N. Garg, A 3 -approximation for the minimum tree spanning k vertices. In Proc. FOCS (1996) 302-309. MR1450628
  22. [22] L. Gouveia, Multicommodity flow models for spanning tree with hop constraints. Eur. J. Oper. Res. 95 (1996) 178-190. Zbl0947.90513
  23. [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. [24] L. Gouveia and E. Janssen, Designing reliable tree with two cable technologies. Eur. J. Oper. Res. 105 (1998) 552-568. Zbl0955.90009
  25. [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. [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. [27] R. Hassin and S. Khuller, z -approximations. J. Algorithms 41 (2002) 429-442. Zbl1014.68222MR1869261
  28. [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. [29] D. Hochbaum, Approximation algorithms for NP-hard problems. P.W.S (1997). Zbl05899342
  30. [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. [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. [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. [33] D.G. Kirkpatrick and P. Hell, The complexity of a generalized matching problem, in Proc. STOC (1978) 240-245. Zbl1282.68182MR521059
  34. [34] G. Kortsarz and D. Peleg, Approximating shallow-light trees, in Proc. SODA (1997) 103-110. MR1447655
  35. [35] S.R. Kosaraju, J.K. Park and C. Stein, Long tours and short superstrings, in Proc. FOCS (1994) 166-177. 
  36. [36] T. Magnanti and L. Wolsey, Optimal trees, Network models. North-Holland, Handbooks Oper. Res. Management Sci. 7 (1995) 503-615. Zbl0839.90135MR1420874
  37. [37] P. Manyem and M.F.M. Stallmann, Some approximation results in multicasting, Working Paper. North Carolina State University (1996). 
  38. [38] 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. Zbl0940.68062
  39. [39] J. Monnot, Families of critical instances and polynomial approximation, Ph.D. Thesis. LAMSADE, Université Paris IX, Dauphine (1998) (in French). 
  40. [40] J. Monnot, The maximum f -depth spanning tree problem. Inform. Process. Lett. 80 (2001) 179-187. Zbl1032.68087MR1859339
  41. [41] J. Monnot, V.Th. Paschos and S. Toulouse, Differential approximation results for traveling salesman problem with distance 1 and 2 (extended abstract). Proc. FCT 2138 (2001) 275-286. Zbl1003.90035MR1914277
  42. [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. [43] J.S. Naor and B. Schieber, Improved approximations for shallow-light spanning trees, in Proc. FOCS (1997) 536-541. 
  44. [44] C.S. Orloff, A fundamental problem in vehicle routing. Networks 4 (1974) 35-64. Zbl0368.90130MR332133
  45. [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. [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. [47] S. Sahni and T. Gonzalez, P-complete approximation problems. J. ACM 23 (1976) 555-565. Zbl0348.90152MR408313
  48. [48] S.A. Vavasis, Approximation algorithms for indefinite quadratic programming. Math. Programming 57 (1972) 279-311. Zbl0845.90095MR1195028
  49. [49] E. Zemel, Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res. 6 (1981) 319-332. Zbl0538.90065MR629633

NotesEmbed ?

top

You must be logged in to post comments.