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\left[t\right]$ problem): we respectively provide a $2/(t+1)$- and a $(t+1)/2t$-standard approximation for the minimization and the maximization versions.

@article{RO_2002__36_4_279_0, author = {Monnot, J\'er\^ome}, title = {Differential approximation of {NP-hard} problems with equal size feasible solutions}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {279--297}, publisher = {EDP-Sciences}, volume = {36}, number = {4}, year = {2002}, doi = {10.1051/ro:2003008}, zbl = {1037.90059}, mrnumber = {1997926}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2003008/} }

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 SP - 279 EP - 297 VL - 36 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2003008/ DO - 10.1051/ro:2003008 LA - en ID - RO_2002__36_4_279_0 ER -

%0 Journal Article %A Monnot, Jérôme %T Differential approximation of NP-hard problems with equal size feasible solutions %J RAIRO - Operations Research - Recherche Opérationnelle %D 2002 %P 279-297 %V 36 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2003008/ %R 10.1051/ro:2003008 %G en %F RO_2002__36_4_279_0

Monnot, Jérôme. Differential approximation of NP-hard problems with equal size feasible solutions. RAIRO - Operations Research - Recherche Opérationnelle, Volume 36 (2002) no. 4, pp. 279-297. doi : 10.1051/ro:2003008. http://archive.numdam.org/articles/10.1051/ro:2003008/

[1] Finding $k$ points with minimum diameter and related problems. J. Algorithms 12 (1991) 38-56. | MR | Zbl

, , and ,[2] A new evaluation function for approximation. Sem. IRIA (1977).

, , and ,[3] Approximating the minimum rooted spanning tree with depth two. Int. Trans. Oper. Res. 6 (1999) 607-622. | MR

and ,[4] Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Verlag (1999). | MR | Zbl

, , , , and ,[5] Approximate solutions of NP-optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. | MR | Zbl

, and ,[6] Structure preserving reductions among convex optimization problems. J. Comput. System Sci. 21 (1980) 136-153. | Zbl

, and ,[7] Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 338 Grad School of Indistrial Administration, CMU (1976).

,[8] Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci. 23 (1977) 789-810. | MR | Zbl

, and ,[9] A compendium of NP-optimization problems. Available on www address: http://www.nada.kth.se/ viggo/problemlist/compendium.html (1998).

and ,[10] Completness in approximation classes. Inform. and Comput. 93 (1991) 241-262. | MR | Zbl

and ,[11] 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. | MR | Zbl

, and ,[12] Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. | MR | Zbl

, and ,[13] Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett. 12 (1999) 127-133. | MR | Zbl

, and ,[14] Differential approximation results for the Steiner tree problem. Appl. Math. Lett. (to appear). | MR | Zbl

, and ,[15] On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci. 156 (1996)117-141. | MR | Zbl

and ,[16] Arc routing problems, part II: The rural postman problem. Oper. Res. (Survey, Expository and Tutorial) 43 (1995) 399-414. | MR | Zbl

, and ,[17] 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). | MR

and ,[18] An analysis of approximations for finding a maximum weight hamiltonian circuit. Oper. Res. 27 (1979) 799-809. | MR | Zbl

, and ,[19] Approximation algorithm for some postman problems. J. ACM 26 (1979) 538-554. | MR | Zbl

,[20] Computers and intractability. A guide to the theory of NP-completeness. CA. Freeman (1979). | MR | Zbl

and ,[21] A $3$-approximation for the minimum tree spanning $k$ vertices. In Proc. FOCS (1996) 302-309. | MR

,[22] Multicommodity flow models for spanning tree with hop constraints. Eur. J. Oper. Res. 95 (1996) 178-190. | Zbl

,[23] Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. J. Comput. 10 (1998) 180-188. | MR | Zbl

,[24] Designing reliable tree with two cable technologies. Eur. J. Oper. Res. 105 (1998) 552-568. | Zbl

and ,[25] Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 4 (2000) 422-437. | Zbl

, , and ,[26] Finding subsets maximizing minimum structures, in Proc. SODA (1995) 150-159. | MR | Zbl

, , and ,[27] $z$-approximations. J. Algorithms 41 (2002) 429-442. | MR | Zbl

and ,[28] An approximation algorithm for maximum packing of 3-edge paths. Inform. Process. Lett. 6 (1997) 63-67. | MR

and ,[29] Approximation algorithms for NP-hard problems. P.W.S (1997).

,[30] Analysis of christofides' heuristic: Some paths are more difficult than cycles. Oper. Res. Lett. 10 (1991) 291-295. | Zbl

,[31] 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. | MR | Zbl

and ,[32] Reducibility among combinatorial problems, edited by R.E Miller and J.W. Thatcher, Complexity of Computer Computations. Plenum Press, NY (1972) 85-103. | MR

,[33] The complexity of a generalized matching problem, in Proc. STOC (1978) 240-245. | MR

and ,[34] Approximating shallow-light trees, in Proc. SODA (1997) 103-110. | MR

and ,[35] Long tours and short superstrings, in Proc. FOCS (1994) 166-177.

, and ,[36] Optimal trees, Network models. North-Holland, Handbooks Oper. Res. Management Sci. 7 (1995) 503-615. | MR | Zbl

and ,[37] Some approximation results in multicasting, Working Paper. North Carolina State University (1996).

and ,[38] 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. | Zbl

,[39] Families of critical instances and polynomial approximation, Ph.D. Thesis. LAMSADE, Université Paris IX, Dauphine (1998) (in French).

,[40] The maximum $f$-depth spanning tree problem. Inform. Process. Lett. 80 (2001) 179-187. | MR | Zbl

,[41] Differential approximation results for traveling salesman problem with distance $1$ and $2$ (extended abstract). Proc. FCT 2138 (2001) 275-286. | MR | Zbl

, and ,[42] Approximation polynomiale des problèmes NP-difficiles: optima locaux et rapport différentiel. Édition HERMÈS Science Lavoisier (2003). | Zbl

, and ,[43] Improved approximations for shallow-light spanning trees, in Proc. FOCS (1997) 536-541.

and ,[44] A fundamental problem in vehicle routing. Networks 4 (1974) 35-64. | MR | Zbl

,[45] On approximation preserving reductions: Complete problems and robust measures, Technical Report C-1987-28. Department of Computer Science, University of Helsinki (1987).

and ,[46] Spanning tree short or small. SIAM J. Discrete Math. 9 (1996) 178-200. | MR | Zbl

, , , and ,[47] P-complete approximation problems. J. ACM 23 (1976) 555-565. | MR | Zbl

and ,[48] Approximation algorithms for indefinite quadratic programming. Math. Programming 57 (1972) 279-311. | MR | Zbl

,[49] Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res. 6 (1981) 319-332. | MR | Zbl

,*Cited by Sources: *