{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T05:47:28Z","timestamp":1773899248004,"version":"3.50.1"},"reference-count":125,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1051\/ro\/2011114","type":"journal-article","created":{"date-parts":[[2011,12,16]],"date-time":"2011-12-16T10:48:26Z","timestamp":1324032506000},"page":"241-294","source":"Crossref","is-referenced-by-count":14,"title":["A survey on combinatorial optimization in dynamic environments"],"prefix":"10.1051","volume":"45","author":[{"given":"Nicolas","family":"Boria","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis T.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2011,12,16]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Albers, On randomized online scheduling, inProceedings of the thiry-fourth annual ACM symposium on Theory of computing, ACM (2002) 134\u2013143.","DOI":"10.1145\/509907.509930"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Albers S., Online algorithms: a survey.Math. Program.97(2003) 3\u201326.","DOI":"10.1007\/s10107-003-0436-0"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Archetti C., Bertazzi L. and Speranza M.G., Reoptimizing the traveling salesman problem.Networks42(2003) 154\u2013159.","DOI":"10.1002\/net.10091"},{"key":"R4","unstructured":"Archetti C., Bertazzi L. and Speranza M.G., Reoptimizing the 0-1 knapsack problem.Discrete Appl. Math.158(2010) 1879\u20131887."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"T. Asano, K. Hori, T. Ono and T. Hirata, A theoretical framework of hybrid approaches to max sat, inISAAC,Lecture Notes in Computer Science1350, edited by H.W. Leong, H. Imai and S. Jain. Springer (1997) 153\u2013162.","DOI":"10.1007\/3-540-63890-3_18"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Ausiello G., Italiano G.F., Marchetti-Spaccamela A. and Nanni U., Incremental algorithms for minimal length paths.J. Algorithms12(1991) 615\u2013638.","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Ausiello G., Feuerstein E., Leonardi S., Stougie L. and Talamo M., Algorithms for the on-line traveling salesman problem.Algorithmica29(2001) 560\u2013581.","DOI":"10.1007\/s004530010071"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. Ausiello, B. Escoffier, J. Monnot and V.Th. Paschos, Reoptimization of minimum and maximum traveling salesman\u2019s tours, inSWAT,Lecture Notes in Computer Science4059, edited by L. Arge and R. Freivalds. Springer (2006) 196\u2013207.","DOI":"10.1007\/11785293_20"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Ausiello G., Escoffier B., Monnot J. and Paschos V.Th., Reoptimization of minimum and maximum traveling salesman\u2019s tours.J. Discrete Algorithms7(2009) 453\u2013463.","DOI":"10.1016\/j.jda.2008.12.001"},{"key":"R10","unstructured":"G. Ausiello, V. Bonifaci and B. Escoffier, Complexity and approximation in reoptimization.Cahier du LAMSADE281. Universit\u00e9 Paris-Dauphine (2008)."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Averbakh I. and Berman O., Probabilistic sales-delivery man and sales-delivery facility location problems on a tree.Transp. Sci.29(1995) 184.","DOI":"10.1287\/trsc.29.2.184"},{"key":"R12","unstructured":"Averbakh I., Berman O. and Simchi-Levi D., Probabilistica priorirouting-location problems.Nav. Res. Logist.41(1994) 973\u2013989."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda R. and Even S., A linear-time approximation algorithm for the weighted vertex cover problem.J. Algorithms2(1981) 198\u2013203.","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"R14","unstructured":"Bartusch M., M\u00f6hring R.H. and Radermacher F.J., A conceptional outline of a DSS for scheduling problems in the building industry.Decis. Support Syst.5(1989) 321\u2013344."},{"key":"R15","unstructured":"Bartusch M., M\u00f6hring R.H. and Radermacher F.J., Design aspects of an advanced model-oriented DSS for scheduling problems in civil engineering.Decis. Support Syst.5(1989) 321\u2013344."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Beardwood, J.H Halton and J.M Hammersley, The shortest path through many points, inMathematical Proceedings of the Cambridge Philosophical Society55. Cambridge Univ Press (1959) 299\u2013327.","DOI":"10.1017\/S0305004100034095"},{"key":"R17","unstructured":"M. Bellalouna,Probl\u00e8mes d\u2019optimisation combinatoires probabilistes. Ph.D. thesis, \u00c9cole Nationale des Ponts et Chauss\u00e9es, Paris, France (1993)."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Bellalouna, S. Souissi and B. Ycart, Average-Case Analysis for the Probabilistic Bin Packing Problem, inMathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities(2004) 149\u2013159.","DOI":"10.1007\/978-3-0348-7915-6_15"},{"key":"R19","unstructured":"Bern M. and Plassmann P., The Steiner problem with edge lengths 1 and 2.Inf. Proc. Lett.32(1989) 171\u2013176."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Berenguer X., A characterization of linear admissible transformations for the m-travelling salesmen problem.Eur. J. Oper. Res.3(1979) 232\u2013238.","DOI":"10.1016\/0377-2217(79)90143-7"},{"key":"R21","unstructured":"D.J. Bertsimas,Probabilistic combinatorial optimization problems. Ph.D. thesis, Massachusetts Institute of Technology (1988)."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Bertsimas D.J., Traveling salesman facility location problems.Transp. Sci.23(1989) 184.","DOI":"10.1287\/trsc.23.3.184"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Bertsimas D.J., The probabilistic minimum spanning tree problem.Networks20(1990) 245\u2013275.","DOI":"10.1002\/net.3230200302"},{"key":"R24","unstructured":"Bertsimas D.J., A vehicle routing problem with stochastic demand.Oper. Res.40(1992) 574\u2013585."},{"key":"R25","unstructured":"Bertsimas D.J. and Simchi-Levi D., A new generation of vehicle routing research: robust algorithms, addressing uncertainty.Oper. Res.44(1996) 286\u2013304."},{"key":"R26","unstructured":"Bertsimas D.J., Jaillet P. and Odoni A.R.,A priorioptimization.Oper. Res.38(1990) 1019\u20131033."},{"key":"R27","unstructured":"Bertsimas D.J., Jaillet P. and Odoni A.R.,A priorioptimization.Oper. Res.38(1990) 1019\u20131033."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"D. Bil\u00f2, H.-J. B\u00f6ckenhauer, J. Hromkovic, R. Kr\u00e1lovic, T. M\u00f6mke, P. Widmayer and A. Zych. Reoptimization of steiner trees, inSWAT,Lecture Notes in Computer Science5124, edited by J. Gudmundsson. Springer (2008) 258\u2013269.","DOI":"10.1007\/978-3-540-69903-3_24"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Bil\u00f2, P. Widmayer and A. Zych, Reoptimization of weighted graph and covering problems, inWAOA,Lecture Notes in Computer Science5426, edited by E. Bampis and M. Skutella. Springer (2008) 201\u2013213.","DOI":"10.1007\/978-3-540-93980-1_16"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"D. Bil\u00f2, H.-J. B\u00f6ckenhauer, D. Komm, R. Kr\u00e1lovic, T. M\u00f6mke, S. Seibert and A. Zych, Reoptimization of the shortest common superstring problem, inCPM,Lecture Notes Computer Science5577, edited by G. Kucherov and E. Ukkonen. Springer (2009) 78\u201391.","DOI":"10.1007\/978-3-642-02441-2_8"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Blom M., Krumke S., De Paepe W. and Stougie L., The online-TSP against fair adversaries.Algorithms and Complexity(2000) 137\u2013149.","DOI":"10.1007\/3-540-46521-9_12"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer H.-J. and Komm D., Reoptimization of the metric deadline TSP.J. Discrete Algorithms8(2010) 87\u2013100.","DOI":"10.1016\/j.jda.2009.04.001"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti and P. Widmayer, Reusing optimal TSP solutions for locally modified input instances, inIFIP TCS IFIP209, edited by G. Navarro, L.E. Bertossi and Y. Kohayakawa. Springer (2006) 251\u2013270.","DOI":"10.1007\/978-0-387-34735-6_21"},{"key":"R34","unstructured":"B\u00f6ckenhauer H.-J., Forlizzi L., Hromkovic J., Kneis J., Kupke J., Proietti G. and Widmayer P., On the approximability of TSP on local modifications of optimally solved instances.Algorithmic Operations Research2(2007) 83\u201393."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovic, T. M\u00f6mke and P. Widmayer, On the hardness of reoptimization, inSOFSEM,Lecture Notes in Computer Science4910, edited by V. Geffert, J. Karhum\u00e4ki, A. Bertoni, B. Preneel, P. N\u00e1vrat and M. Bielikov\u00e1. Springer (2008) 50\u201365.","DOI":"10.1007\/978-3-540-77566-9_5"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer H.-J., Hromkovic J., Kr\u00e1lovic R., M\u00f6mke T. and Rossmanith P., Reoptimization of steiner trees: Changing the terminal set.Theor. Comput. Sci.410(2009) 3428\u20133435.","DOI":"10.1016\/j.tcs.2008.04.039"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, K. Freiermuth, J. Hromkovic, T. M\u00f6mke, A. Sprock and B. Steffen, The steiner tree reoptimization problem with sharpened triangle inequality, inCIAC,Lecture Notes in Computer Science6078, edited by T. Calamoneri and J. D\u00edaz. Springer (2010) 180\u2013191.","DOI":"10.1007\/978-3-642-13073-1_17"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"Boria N. and Paschos V.T., Fast reoptimization for the minimum spanning tree problem.J. Discrete Algorithms8(2010) 296\u2013310.","DOI":"10.1016\/j.jda.2009.07.002"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"N. Boria, C. Murat and V.T. Paschos, On the probabilistic min spanning tree problem, inIMCSIT(2010) 893\u2013900.","DOI":"10.1109\/IMCSIT.2010.5679920"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"N. Boria, J. Monnot and V. Th. Paschos,Reoptimization of maximum weight induced hereditary subgraph problems. Cahier du LAMSADE 311, LAMSADE, Universit\u00e9 Paris-Dauphine (2011).","DOI":"10.1007\/978-3-642-29344-3_7"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"N. Boria, J. Monnot and V. Th. Paschos, Reoptimization of the maximum weightPk-free subgraph under vertex insertion, inProc. Workshop on Algorithms and Computation, WALCOM\u201912,Lect. Notes Comput. Sci.Springer-Verlag (2011), to appear.","DOI":"10.1007\/978-3-642-28076-4_10"},{"key":"R42","unstructured":"N. Boria, C. Murat and V. Th. Paschos, On the probabilistic min spanning tree problem.J. Mathematical Modelling and Algorithms. To appear."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"Bourgeois N., Della Croce F., Escoffier B., Murat C. and Paschos V.Th., Probabilistic graph-coloring in bipartite and split graphs.J. Combin. Optim.17(2009) 274\u2013311.","DOI":"10.1007\/s10878-007-9112-2"},{"key":"R44","unstructured":"Bouyahia Z., Bellalouna M., Jaillet P. and Ghedira K.,A prioriparallel machines scheduling.Comput. Ind. Eng.58(2010) 488\u2013500."},{"key":"R45","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, B. Godfrey, S. Rao and K. Talwar, Paths, trees, and minimum latency tours, inFOCS. IEEE Computer Society (2003) 36\u201345.","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"R46","unstructured":"N. Christofides,Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)."},{"key":"R47","unstructured":"Demange M. and Paschos V.T., On-line vertex-covering.Theor. Comput. Sci.332(2005) 83\u2013108."},{"key":"R48","unstructured":"M. Demange and B. Leroy-Beaulieu,Online coloring of comparability graphs: some results. Report, Chair ROSE-2007-001, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (2007)."},{"key":"R49","doi-asserted-by":"crossref","unstructured":"M. Demange, X. Paradon and V.Th. Paschos, On-line maximum-order induced hereditary subgraph problems, inSOFSEM 2000 \u2013 Theory and Practice of Informatics,Lecture Notes in Computer Science1963, edited by V. Hlavc\u00e1\u02c7, K. G. Jeffery and J. Wiedermann. Springer-Verlag (2000) 326\u2013334.","DOI":"10.1007\/3-540-44411-4_21"},{"key":"R50","unstructured":"Demange M., Paradon X. and Paschos V.Th., On-line maximum-order induced hereditary subgraph problems.Int. Trans. Operat. Res.12(2005) 185\u2013201."},{"key":"R51","unstructured":"M. Demange, G. Di Stefano and B. Leroy-Beaulieu, On the online track assignment problem.Discrete Appl. Math.To appear."},{"key":"R52","doi-asserted-by":"crossref","unstructured":"Demetrescu C. and Italiano G.F., A new approach to dynamic all pairs shortest paths.J. ACM51(2004) 968\u2013992.","DOI":"10.1145\/1039488.1039492"},{"key":"R53","unstructured":"Dertouzos M.L. and Mok A.K., Multiprocessor online scheduling of hard-real-time tasks.IEEE Trans. Softw. Eng.15(2002) 1497\u20131506."},{"key":"R54","doi-asserted-by":"crossref","unstructured":"Eppstein D., Galil Z., Italiano G.F. and Nissenzweig A., Sparsification \u2013 a technique for speeding up dynamic graph algorithms.J. ACM44(1997) 669\u2013696.","DOI":"10.1145\/265910.265914"},{"key":"R55","unstructured":"Escoffier B., Milanic M. and Paschos V.Th., Simple and fast reoptimizations for the steiner tree problem.Algorithmic Operations Research4(2009) 86\u201394."},{"key":"R56","unstructured":"Even S. and Gazit H., Updating distances in dynamic graphs.Methods Oper. Res.49(1985) 371\u2013387."},{"key":"R57","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Singh, Improved approximation ratios for traveling salesperson tours and paths in directed graphs, inAPPROX-RANDOM,Lecture Notes in Computer Science4627, edited by M. Charikar, K. Jansen, O. Reingold and J.D.P. Rolim. Springer (2007) 104\u2013118.","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"R58","unstructured":"Frederickson G.N., Data structures for on-line updating of minimum spanning trees, with applications.SIAM J. Comput.14(1985) 781\u2013798."},{"key":"R59","unstructured":"Frederickson G.N., Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees.SIAM J. Comput.26(1997) 484\u2013538."},{"key":"R60","unstructured":"Frieze A.M., On the value of a random minimum spanning tree problem.Discrete Appl. Math.10(1985) 47\u201356."},{"key":"R61","doi-asserted-by":"crossref","unstructured":"Frieze A.M., Galbiati G. and Maffioli F., On the worst-case performance of some algorithms for the asymmetric traveling salesman problem.Networks12(1982) 23\u201339.","DOI":"10.1002\/net.3230120103"},{"key":"R62","doi-asserted-by":"crossref","unstructured":"Frigioni D., Marchetti-Spaccamela A. and Nanni U., Fully dynamic algorithms for maintaining shortest paths trees.J. Algorithms34(2000) 251\u2013281.","DOI":"10.1006\/jagm.1999.1048"},{"key":"R63","unstructured":"Gabrel V., Moulet A., Murat C. and Paschos V.T., A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts.A. Oper. Res.69(1997) 115\u2013134."},{"key":"R64","doi-asserted-by":"crossref","unstructured":"Gallant J., Maier D. and Storer J.A., On finding minimal length superstrings.J. Comput. Syst. Sci.20(1980) 50\u201358.","DOI":"10.1016\/0022-0000(80)90004-5"},{"key":"R65","doi-asserted-by":"crossref","unstructured":"Hall N.G. and Posner M.E., Sensitivity analysis for scheduling problems.J. Scheduling7(2004) 49\u201383.","DOI":"10.1023\/B:JOSH.0000013055.31639.f6"},{"key":"R66","unstructured":"M.M. Halld\u00f3rsson, Online coloring known graphs, inProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics (1999) 918."},{"key":"R67","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson M.M. and Radhakrishnan J., Greed is good: Approximating independent sets in sparse and bounded-degree graphs.Algorithmica18(1997) 145\u2013163.","DOI":"10.1007\/BF02523693"},{"key":"R68","unstructured":"Halld\u00f3rsson M.M., Iwama K., Miyazaki S. and Taketomi S., Online independent sets.Theor. Comput. Sci.289(2002) 953\u2013962."},{"key":"R69","unstructured":"Hassin R. and Rubinstein S., A 7\/8-approximation algorithm for metric Max TSP.Inf. Proc. Lett.81(2002) 247\u2013251."},{"key":"R70","unstructured":"Henzinger M.R., Improved data structures for fully dynamic biconnectivity.SIAM J. Comput.29(2000) 1761\u20131815."},{"key":"R71","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger and V. King, Fully dynamic biconnectivity and transitive closure, inFOCS. IEEE Computer Society (1995) 664\u2013672.","DOI":"10.1109\/SFCS.1995.492668"},{"key":"R72","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger and V. King, Maintaining minimum spanning trees in dynamic graphs, inICALP,Lecture Notes in Computer Science1256, edited by P. Degano, R. Gorrieri and A. Marchetti-Spaccamela. Springer (1997) 594\u2013604.","DOI":"10.1007\/3-540-63165-8_214"},{"key":"R73","doi-asserted-by":"crossref","unstructured":"Henzinger M.R. and King V., Randomized fully dynamic graph algorithms with polylogarithmic time per operation.J. ACM46(1999) 502\u2013516.","DOI":"10.1145\/320211.320215"},{"key":"R74","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger and J.A. La Poutr\u00e9, Certificates and fast algorithms for biconnectivity in fully-dynamic graphs, inESA,Lecture Notes in Computer Science979, edited by P.G. Spirakis. Springer (1995) 171\u2013184.","DOI":"10.1007\/3-540-60313-1_142"},{"key":"R75","doi-asserted-by":"crossref","unstructured":"Holm J., de Lichtenberg K. and Thorup M., Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.J. ACM48(2001) 723\u2013760.","DOI":"10.1145\/502090.502095"},{"key":"R76","unstructured":"L. Horchani and M. Bellalouna, The 2-dimensional probabilistic bin packing problem: an average case analysis of the FBS algorithm, inProceedings of the American Conference on Applied Mathematics. World Scientific and Engineering Academy and Society (WSEAS) (2008) 449\u2013453."},{"key":"R77","doi-asserted-by":"crossref","unstructured":"Ibarra O.H. and Kim C.E., Fast approximation algorithms for the knapsack and sum of subset problems.J. ACM22(1975) 463\u2013468.","DOI":"10.1145\/321906.321909"},{"key":"R78","doi-asserted-by":"crossref","unstructured":"Z. Ivkovi\u0107 and E.L. Lloyd, Fully dynamic maintenance of vertex cover, inGraph-Theoretic Concepts in Computer Science. Springer (1994) 99\u2013111.","DOI":"10.1007\/3-540-57899-4_44"},{"key":"R79","doi-asserted-by":"crossref","unstructured":"Ivkovi\u0107 Z. and Lloyd E.L., Fully dynamic algorithms for bin packing: Being (mostly) myopic helps.SIAM J. Comput.28(1998) 574\u2013611.","DOI":"10.1137\/S0097539794276749"},{"key":"R80","unstructured":"P. Jaillet,Probabilistic traveling salesman problems. Ph.D. thesis, Massachusetts Institute of Technology (1985)."},{"key":"R81","unstructured":"Jaillet P.,A priorisolution of a traveling salesman problem in which a random subset of the customers are visited.Oper. Res.36(1988) 929\u2013936."},{"key":"R82","doi-asserted-by":"crossref","unstructured":"Jaillet P., Shortest path problems with node failures.Networks22(1992) 589\u2013605.","DOI":"10.1002\/net.3230220607"},{"key":"R83","unstructured":"Jaillet P., Analysis of probabilistic combinatorial optimization problems in Euclidean spaces.Math. Oper. Res.18(1993) 51\u201370."},{"key":"R84","unstructured":"P. Jaillet and A.R. Odoni, The probabilistic vehicle routing problem, inVehicle routing: Methods and Studies, edited by B.L. Golden and A.A. Assad. North Holland, Amsterdam (1988) 293\u2013318."},{"key":"R85","unstructured":"Jaillet P. and Wagner M.R., Online routing problems: Value of advanced information as improved competitive ratios.Transp. Sci.40(2006) 200\u2013210."},{"key":"R86","unstructured":"D.S. Johnson,Near-optimal bin packing algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1973)."},{"key":"R87","doi-asserted-by":"crossref","unstructured":"Johnson D.S., Fast algorithms for bin packing.J. Comput. Syst. Sci.8(1974) 272\u2013314.","DOI":"10.1016\/S0022-0000(74)80026-7"},{"key":"R88","doi-asserted-by":"crossref","unstructured":"Johnson D.S. and Garey M.R., A 71\/60 theorem for bin packing.J. Complex.1(1985) 65\u2013106.","DOI":"10.1016\/0885-064X(85)90022-6"},{"key":"R89","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, inFOCS, Chicago, IEEE Computer Society Illinois (1982) 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"R90","unstructured":"Karp R.M., Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane.Math. Oper. Res.2(1977) 209\u2013224."},{"key":"R91","doi-asserted-by":"crossref","unstructured":"Karp R.M., A patching algorithm for the nonsymmetric traveling-salesman problem.SIAM J. Comput.8(1979) 561.","DOI":"10.1137\/0208045"},{"key":"R92","doi-asserted-by":"crossref","unstructured":"V. King, Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, inFOCS. IEEE Computer Society (1999) 81\u201391.","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"R93","doi-asserted-by":"crossref","unstructured":"Klein P.N. and Subramanian S., A fully dynamic approximation scheme for shortest paths in planar graphs.Algorithmica22(1998) 235\u2013249.","DOI":"10.1007\/PL00009223"},{"key":"R94","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju, J.K. Park and C. Stein, Long tours and short superstrings (preliminary version), inFOCS. IEEE Computer Society (1994) 166\u2013177.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"R95","doi-asserted-by":"crossref","unstructured":"J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, inProceedings of the American Mathematical Society7(1956).","DOI":"10.2307\/2033241"},{"key":"R96","unstructured":"P.S. Loubal,A network evaluation procedure. Bay Area Transportation Study Commission (1967)."},{"key":"R97","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, inProc. ICALP\u201993,Lecture Notes in Computer Science700. edited by A. Lingas, R.G. Karlsson and S. Carlsson. Springer-Verlag (1993) 40\u201351.","DOI":"10.1007\/3-540-56939-1_60"},{"key":"R98","unstructured":"Miltersen P.B., Subramanian S., Vitter J.S. and Tamassia R., Complexity models for incremental computation.Theor. Comput. Sci.130(1994) 203\u2013236."},{"key":"R99","doi-asserted-by":"crossref","unstructured":"Murat C. and Paschos V.Th., The probabilistic longest path problem.Networks33(1999) 207\u2013219.","DOI":"10.1002\/(SICI)1097-0037(199905)33:3<207::AID-NET7>3.3.CO;2-Z"},{"key":"R100","unstructured":"Murat C. and Paschos V.Th.,A priorioptimization for the probabilistic maximum independent set problem.Theor. Comput. Sci.270(2002) 561\u2013590."},{"key":"R101","unstructured":"Murat C. and Paschos V.Th., The probabilistic minimum vertex-covering problem.Int. Trans. Oper. Res.9(2002) 19\u201332."},{"key":"R102","doi-asserted-by":"crossref","unstructured":"C. Murat and V. Paschos, The probabilistic minimum coloring problem, inGraph-Theoretic Concepts in Computer Science, Springer (2003) 346\u2013357.","DOI":"10.1007\/978-3-540-39890-5_30"},{"key":"R103","unstructured":"Murat C. and Paschos V.T., On the probabilistic minimum coloring and minimum k-coloring.Discrete Appl. Math.154(2006) 564\u2013586."},{"key":"R104","doi-asserted-by":"crossref","unstructured":"C. Murat and V.T. Paschos,Probabilistic combinatorial optimization on graphs. Wiley Online Library (2006).","DOI":"10.1002\/9780470612507"},{"key":"R105","unstructured":"J. Murchland,The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. London Businness School, Transport Network Theory Unit (1967)."},{"key":"R106","unstructured":"Papadimitriou C.H. and Yannakakis M., The traveling salesman problem with distances one and two.Math. Oper. Res.18(1993) 1\u201311."},{"key":"R107","unstructured":"Paz A. and Moran S., Non deterministic polynomial optimization problems and their approximations.Theor. Comput. Sci.15(1981) 251\u2013277."},{"key":"R108","unstructured":"K. Pruhs, E. Torng and J. Sgall, Online scheduling, inHandbook of Scheduling: Algorithms, Models, and Performance Analysis, edited by Joseph Y.-T. Leung, Chapter 15. CRC Press (2004) 15-1\u201315-41."},{"key":"R109","unstructured":"Richey M.B., Improved bounds for harmonic-based bin-packing algorithms.Discrete Appl. Math.3(1991) 203\u2013227."},{"key":"R110","doi-asserted-by":"crossref","unstructured":"Robertson N. and Seymour P.D., Graph minors. XX. Wagner\u2019s conjecture.J. Comb. Theory, Ser. B92(2004) 325\u2013357.","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"R111","unstructured":"G. Robins and A. Zelikovsky, Improved steiner tree approximation in graphs, inSODA(2000) 770\u2013779."},{"key":"R112","doi-asserted-by":"crossref","unstructured":"Rodionov V.V., The parametric problem of shortest distances.USSR Comput. Math. Math. Phys.8(1968) 336\u2013343.","DOI":"10.1016\/0041-5553(68)90148-1"},{"key":"R113","doi-asserted-by":"crossref","unstructured":"H. Rohnert, A dynamization of the all pairs least cost path problem, inSTACS,Lecture Notes in Computer Science182, edited by K. Mehlhorn. Springer (1985) 279\u2013286.","DOI":"10.1007\/BFb0024016"},{"key":"R114","doi-asserted-by":"crossref","unstructured":"Sahni S. and Gonzalez T.F., P-complete approximation problems.J. ACM23(1976) 555\u2013565.","DOI":"10.1145\/321958.321975"},{"key":"R115","doi-asserted-by":"crossref","unstructured":"Sch\u00e4ffter M.W., Scheduling with forbidden sets.Discrete Appl. Math.72(1997) 155\u2013166.","DOI":"10.1016\/S0166-218X(96)00042-X"},{"key":"R116","unstructured":"Seguin R., Probl\u00e8mes stochastiques de tourn\u00e9es de v\u00e9hicules: un pas de plus vers le r\u00e9alisme.Cahiers du Centre d\u2019\u00e9tudes de recherche op\u00e9rationnelle35(1993) 187\u2013226."},{"key":"R117","unstructured":"J. Sgall, On-line scheduling-a survey, inOnline Algorithms: The State of the Art, edited by A. Fiat and G.J. Woeginger,Lect. Notes Comput. Sci.1442. Springer (1998) 196\u2013231. (1997)."},{"key":"R118","doi-asserted-by":"crossref","unstructured":"R. Sitters, The minimum latency problem is np-hard for weighted trees, inIPCO,Lecture Notes in Computer Science2337, edited by W. Cook and A.S. Schulz. Springer (2002) 230\u2013239.","DOI":"10.1007\/3-540-47867-1_17"},{"key":"R119","doi-asserted-by":"crossref","unstructured":"Sleator D.D. and Tarjan R.E., A data structure for dynamic trees.J. Comput. Syst. Sci.26(1983) 362\u2013391.","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"R120","unstructured":"Steele J.M., Subadditive Euclidean functionals and nonlinear growth in geometric probability.Ann. Probab.9(1981) 365\u2013376."},{"key":"R121","unstructured":"Steele J.M., On Frieze\u2019s\u03c7(3) limit for lengths of minimal spanning trees.Discrete Appl. Math.18(1987) 99\u2013103."},{"key":"R122","unstructured":"Sweedyk Z., A 2+1\/2-approximation algorithm for shortest superstring.SIAM J. Comput.29(1999) 954\u2013986."},{"key":"R123","unstructured":"Van Vliet A., An improved lower bound for on-line bin-packing algorithms.Inf. Proc. Lett.43(1992) 277\u2013284."},{"key":"R124","doi-asserted-by":"crossref","unstructured":"V. Vassilevska, Explicit inapproximability bounds for the shortest superstring problem, inMFCS,Lecture Notes in Computer Science3618, edited by J. Jedrzejowicz and A. Szepietowski. Springer (2005) 793\u2013800.","DOI":"10.1007\/11549345_68"},{"key":"R125","unstructured":"Wagner A., On finite affine line transitive planes.Math. Zeitschr.87(1965) 1\u201311."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2011114\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T23:16:38Z","timestamp":1742080598000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2011114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":125,"journal-issue":{"issue":"3"},"alternative-id":["ro110015"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2011114","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7]]}}}