A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria; Vangelis T. Paschos

RAIRO - Operations Research (2011)

  • Volume: 45, Issue: 3, page 241-294
  • ISSN: 0399-0559

Abstract

top
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The second framework is probabilistic optimization, where the instance to optimize is not fully known at the time when a solution is to be proposed, but results from a determined Bernoulli process. Then, the goal is to compute a solution with optimal expected value.

How to cite

top

Boria, Nicolas, and Paschos, Vangelis T.. "A survey on combinatorial optimization in dynamic environments∗." RAIRO - Operations Research 45.3 (2011): 241-294. <http://eudml.org/doc/276362>.

@article{Boria2011,
abstract = {This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The second framework is probabilistic optimization, where the instance to optimize is not fully known at the time when a solution is to be proposed, but results from a determined Bernoulli process. Then, the goal is to compute a solution with optimal expected value.},
author = {Boria, Nicolas, Paschos, Vangelis T.},
journal = {RAIRO - Operations Research},
keywords = {Approximation; reoptimization; hereditary problem; complexity; graph; on-line algorithms; probabilistic optimization; approximation},
language = {eng},
month = {12},
number = {3},
pages = {241-294},
publisher = {EDP Sciences},
title = {A survey on combinatorial optimization in dynamic environments∗},
url = {http://eudml.org/doc/276362},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Boria, Nicolas
AU - Paschos, Vangelis T.
TI - A survey on combinatorial optimization in dynamic environments∗
JO - RAIRO - Operations Research
DA - 2011/12//
PB - EDP Sciences
VL - 45
IS - 3
SP - 241
EP - 294
AB - This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The second framework is probabilistic optimization, where the instance to optimize is not fully known at the time when a solution is to be proposed, but results from a determined Bernoulli process. Then, the goal is to compute a solution with optimal expected value.
LA - eng
KW - Approximation; reoptimization; hereditary problem; complexity; graph; on-line algorithms; probabilistic optimization; approximation
UR - http://eudml.org/doc/276362
ER -

References

top
  1. S. Albers, On randomized online scheduling, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, ACM (2002) 134–143.  Zbl1192.68091
  2. S. Albers, Online algorithms: a survey. Math. Program.97 (2003) 3–26.  Zbl1035.68136
  3. C. Archetti, L. Bertazzi and M.G. Speranza, Reoptimizing the traveling salesman problem. Networks42 (2003) 154–159.  Zbl1053.90126
  4. C. Archetti, L. Bertazzi and M.G. Speranza, Reoptimizing the 0-1 knapsack problem. Discrete Appl. Math.158 (2010) 1879–1887.  Zbl1206.90132
  5. T. Asano, K. Hori, T. Ono and T. Hirata, A theoretical framework of hybrid approaches to max sat, in ISAAC, Lecture Notes in Computer Science1350, edited by H.W. Leong, H. Imai and S. Jain. Springer (1997) 153–162.  
  6. G. Ausiello, G.F. Italiano, A. Marchetti-Spaccamela and U. Nanni, Incremental algorithms for minimal length paths. J. Algorithms12 (1991) 615–638.  Zbl0751.68042
  7. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie and M. Talamo, Algorithms for the on-line traveling salesman problem. Algorithmica29 (2001) 560–581.  Zbl0985.68088
  8. G. Ausiello, B. Escoffier, J. Monnot and V.Th. Paschos, Reoptimization of minimum and maximum traveling salesman’s tours, in SWAT, Lecture Notes in Computer Science4059, edited by L. Arge and R. Freivalds. Springer (2006) 196–207.  Zbl1141.90506
  9. G. Ausiello, B. Escoffier, J. Monnot and V.Th. Paschos, Reoptimization of minimum and maximum traveling salesman’s tours. J. Discrete Algorithms7 (2009) 453–463.  Zbl1180.90259
  10. G. Ausiello, V. Bonifaci and B. Escoffier, Complexity and approximation in reoptimization. Cahier du LAMSADE281. Université Paris-Dauphine (2008).  
  11. I. Averbakh and O. Berman, Probabilistic sales-delivery man and sales-delivery facility location problems on a tree. Transp. Sci.29 (1995) 184.  Zbl0860.90058
  12. I. Averbakh, O. Berman and D. Simchi-Levi, Probabilistic a priori routing-location problems. Nav. Res. Logist.41 (1994) 973–989.  Zbl0830.90086
  13. R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms2 (1981) 198–203.  Zbl0459.68033
  14. M. Bartusch, R.H. Möhring and F.J. Radermacher, A conceptional outline of a DSS for scheduling problems in the building industry. Decis. Support Syst.5 (1989) 321–344.  
  15. M. Bartusch, R.H. Möhring and F.J. Radermacher, Design aspects of an advanced model-oriented DSS for scheduling problems in civil engineering. Decis. Support Syst.5 (1989) 321–344.  
  16. J. Beardwood, J.H Halton and J.M Hammersley, The shortest path through many points, in Mathematical Proceedings of the Cambridge Philosophical Society55. Cambridge Univ Press (1959) 299–327.  Zbl0118.35601
  17. M. Bellalouna, Problèmes d’optimisation combinatoires probabilistes. Ph.D. thesis, École Nationale des Ponts et Chaussées, Paris, France (1993).  
  18. M. Bellalouna, S. Souissi and B. Ycart, Average-Case Analysis for the Probabilistic Bin Packing Problem, in Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities (2004) 149–159.  Zbl1165.68526
  19. M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett.32 (1989) 171–176.  Zbl0677.68074
  20. X. Berenguer, A characterization of linear admissible transformations for the m-travelling salesmen problem. Eur. J. Oper. Res.3 (1979) 232–238.  Zbl0406.90044
  21. D.J. Bertsimas, Probabilistic combinatorial optimization problems. Ph.D. thesis, Massachusetts Institute of Technology (1988).  
  22. D.J. Bertsimas, Traveling salesman facility location problems. Transp. Sci.23 (1989) 184.  Zbl0682.90039
  23. D.J. Bertsimas, The probabilistic minimum spanning tree problem. Networks20 (1990) 245–275.  Zbl0702.90089
  24. D.J. Bertsimas, A vehicle routing problem with stochastic demand. Oper. Res.40 (1992) 574–585.  Zbl0764.90030
  25. D.J. Bertsimas and D. Simchi-Levi, A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Oper. Res.44 (1996) 286–304.  Zbl0855.90053
  26. D.J. Bertsimas, P. Jaillet and A.R. Odoni, A priori optimization. Oper. Res.38 (1990) 1019–1033.  Zbl0721.90062
  27. D.J. Bertsimas, P. Jaillet and A.R. Odoni, A priori optimization. Oper. Res.38 (1990) 1019–1033.  Zbl0721.90062
  28. D. Bilò, H.-J. Böckenhauer, J. Hromkovic, R. Královic, T. Mömke, P. Widmayer and A. Zych. Reoptimization of steiner trees, in SWAT, Lecture Notes in Computer Science5124, edited by J. Gudmundsson. Springer (2008) 258–269.  Zbl1155.68574
  29. D. Bilò, P. Widmayer and A. Zych, Reoptimization of weighted graph and covering problems, in WAOA, Lecture Notes in Computer Science5426, edited by E. Bampis and M. Skutella. Springer (2008) 201–213.  Zbl1209.68632
  30. D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královic, T. Mömke, S. Seibert and A. Zych, Reoptimization of the shortest common superstring problem, in CPM, Lecture Notes Computer Science5577, edited by G. Kucherov and E. Ukkonen. Springer (2009) 78–91.  Zbl1247.68334
  31. M. Blom, S. Krumke, W. De Paepe and L. Stougie, The online-TSP against fair adversaries. Algorithms and Complexity (2000) 137–149.  Zbl0971.68637
  32. H.-J. Böckenhauer and D. Komm, Reoptimization of the metric deadline TSP. J. Discrete Algorithms8 (2010) 87–100.  Zbl1181.90229
  33. H.-J. Böckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti and P. Widmayer, Reusing optimal TSP solutions for locally modified input instances, in IFIP TCS IFIP209, edited by G. Navarro, L.E. Bertossi and Y. Kohayakawa. Springer (2006) 251–270.  
  34. H.-J. Böckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti and P. Widmayer, On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Operations Research2 (2007) 83–93.  Zbl1206.90134
  35. H.-J. Böckenhauer, J. Hromkovic, T. Mömke and P. Widmayer, On the hardness of reoptimization, in SOFSEM, Lecture Notes in Computer Science4910, edited by V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat and M. Bieliková. Springer (2008) 50–65.  Zbl1133.68351
  36. H.-J. Böckenhauer, J. Hromkovic, R. Královic, T. Mömke and P. Rossmanith, Reoptimization of steiner trees: Changing the terminal set. Theor. Comput. Sci.410 (2009) 3428–3435.  Zbl1192.68471
  37. H.-J. Böckenhauer, K. Freiermuth, J. Hromkovic, T. Mömke, A. Sprock and B. Steffen, The steiner tree reoptimization problem with sharpened triangle inequality, in CIAC, Lecture Notes in Computer Science6078, edited by T. Calamoneri and J. Díaz. Springer (2010) 180–191.  Zbl1284.68654
  38. N. Boria and V.T. Paschos, Fast reoptimization for the minimum spanning tree problem. J. Discrete Algorithms8 (2010) 296–310.  Zbl1192.90218
  39. N. Boria, C. Murat and V.T. Paschos, On the probabilistic min spanning tree problem, in IMCSIT (2010) 893–900.  Zbl06137236
  40. N. Boria, J. Monnot and V. Th. Paschos, Reoptimization of maximum weight induced hereditary subgraph problems. Cahier du LAMSADE 311, LAMSADE, Université Paris-Dauphine (2011).  Zbl1277.68085
  41. N. Boria, J. Monnot and V. Th. Paschos, Reoptimization of the maximum weight Pk-free subgraph under vertex insertion, in Proc. Workshop on Algorithms and Computation, WALCOM’12, Lect. Notes Comput. Sci. Springer-Verlag (2011), to appear.  Zbl06044021
  42. N. Boria, C. Murat and V. Th. Paschos, On the probabilistic min spanning tree problem. J. Mathematical Modelling and Algorithms. To appear.  Zbl06176262
  43. N. Bourgeois, F. Della Croce, B. Escoffier, C. Murat and V.Th. Paschos, Probabilistic graph-coloring in bipartite and split graphs. J. Combin. Optim.17 (2009) 274–311.  Zbl1206.05039
  44. Z. Bouyahia, M. Bellalouna, P. Jaillet and K. Ghedira, A priori parallel machines scheduling. Comput. Ind. Eng.58 (2010) 488–500.  
  45. K. Chaudhuri, B. Godfrey, S. Rao and K. Talwar, Paths, trees, and minimum latency tours, in FOCS. IEEE Computer Society (2003) 36–45.  
  46. 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).  
  47. M. Demange and V.T. Paschos, On-line vertex-covering. Theor. Comput. Sci.332 (2005) 83–108.  Zbl1070.68118
  48. M. Demange and B. Leroy-Beaulieu, Online coloring of comparability graphs: some results. Report, Chair ROSE-2007-001, École Polytechnique Fédérale de Lausanne (2007).  
  49. M. Demange, X. Paradon and V.Th. Paschos, On-line maximum-order induced hereditary subgraph problems, in SOFSEM 2000 – Theory and Practice of Informatics, Lecture Notes in Computer Science1963, edited by V. Hlavcáˇ, K. G. Jeffery and J. Wiedermann. Springer-Verlag (2000) 326–334.  
  50. M. Demange, X. Paradon and V.Th. Paschos, On-line maximum-order induced hereditary subgraph problems. Int. Trans. Operat. Res.12 (2005) 185–201.  Zbl1063.90059
  51. M. Demange, G. Di Stefano and B. Leroy-Beaulieu, On the online track assignment problem. Discrete Appl. Math. To appear.  Zbl1238.90088
  52. C. Demetrescu and G.F. Italiano, A new approach to dynamic all pairs shortest paths. J. ACM51 (2004) 968–992.  Zbl1125.68393
  53. M.L. Dertouzos and A.K. Mok, Multiprocessor online scheduling of hard-real-time tasks. IEEE Trans. Softw. Eng.15 (2002) 1497–1506.  
  54. D. Eppstein, Z. Galil, G.F. Italiano and A. Nissenzweig, Sparsification – a technique for speeding up dynamic graph algorithms. J. ACM44 (1997) 669–696.  Zbl0891.68072
  55. B. Escoffier, M. Milanic and V.Th. Paschos, Simple and fast reoptimizations for the steiner tree problem. Algorithmic Operations Research4 (2009) 86–94.  Zbl1277.90138
  56. S. Even and H. Gazit, Updating distances in dynamic graphs. Methods Oper. Res.49 (1985) 371–387.  Zbl0565.05052
  57. U. Feige and M. Singh, Improved approximation ratios for traveling salesperson tours and paths in directed graphs, in APPROX-RANDOM, Lecture Notes in Computer Science4627, edited by M. Charikar, K. Jansen, O. Reingold and J.D.P. Rolim. Springer (2007) 104–118.  Zbl1171.90507
  58. G.N. Frederickson, Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput.14 (1985) 781–798.  Zbl0575.68068
  59. G.N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput.26 (1997) 484–538.  Zbl0874.68081
  60. A.M. Frieze, On the value of a random minimum spanning tree problem. Discrete Appl. Math.10 (1985) 47–56.  Zbl0578.05015
  61. A.M. Frieze, G. Galbiati and F. Maffioli, On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks12 (1982) 23–39.  Zbl0478.90070
  62. D. Frigioni, A. Marchetti-Spaccamela and U. Nanni, Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms34 (2000) 251–281.  Zbl0949.68169
  63. V. Gabrel, A. Moulet, C. Murat and V.T. Paschos, A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts. A. Oper. Res.69 (1997) 115–134.  Zbl0880.90092
  64. J. Gallant, D. Maier and J.A. Storer, On finding minimal length superstrings. J. Comput. Syst. Sci.20 (1980) 50–58.  Zbl0436.68043
  65. N.G. Hall and M.E. Posner, Sensitivity analysis for scheduling problems. J. Scheduling7 (2004) 49–83.  Zbl1306.90052
  66. M.M. Halldórsson, Online coloring known graphs, in Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics (1999) 918.  Zbl0925.68342
  67. M.M. Halldórsson and J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica18 (1997) 145–163.  Zbl0866.68077
  68. M.M. Halldórsson, K. Iwama, S. Miyazaki and S. Taketomi, Online independent sets. Theor. Comput. Sci.289 (2002) 953–962.  Zbl1061.68187
  69. R. Hassin and S. Rubinstein, A 7/8-approximation algorithm for metric Max TSP. Inf. Proc. Lett.81 (2002) 247–251.  Zbl1044.90059
  70. M.R. Henzinger, Improved data structures for fully dynamic biconnectivity. SIAM J. Comput.29 (2000) 1761–1815.  Zbl0953.68042
  71. M.R. Henzinger and V. King, Fully dynamic biconnectivity and transitive closure, in FOCS. IEEE Computer Society (1995) 664–672.  Zbl0938.68919
  72. M.R. Henzinger and V. King, Maintaining minimum spanning trees in dynamic graphs, in ICALP, Lecture Notes in Computer Science1256, edited by P. Degano, R. Gorrieri and A. Marchetti-Spaccamela. Springer (1997) 594–604.  
  73. M.R. Henzinger and V. King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM46 (1999) 502–516.  Zbl1065.68665
  74. M.R. Henzinger and J.A. La Poutré, Certificates and fast algorithms for biconnectivity in fully-dynamic graphs, in ESA, Lecture Notes in Computer Science979, edited by P.G. Spirakis. Springer (1995) 171–184.  
  75. J. Holm, K. de Lichtenberg and M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM48 (2001) 723–760.  Zbl1127.68408
  76. L. Horchani and M. Bellalouna, The 2-dimensional probabilistic bin packing problem: an average case analysis of the FBS algorithm, in Proceedings of the American Conference on Applied Mathematics. World Scientific and Engineering Academy and Society (WSEAS) (2008) 449–453.  
  77. O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM22 (1975) 463–468.  Zbl0345.90049
  78. Z. Ivković and E.L. Lloyd, Fully dynamic maintenance of vertex cover, in Graph-Theoretic Concepts in Computer Science. Springer (1994) 99–111.  
  79. Z. Ivković and E.L. Lloyd, Fully dynamic algorithms for bin packing: Being (mostly) myopic helps. SIAM J. Comput.28 (1998) 574–611.  Zbl0915.68078
  80. P. Jaillet, Probabilistic traveling salesman problems. Ph.D. thesis, Massachusetts Institute of Technology (1985).  
  81. P. Jaillet, A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res.36 (1988) 929–936.  Zbl0665.90096
  82. P. Jaillet, Shortest path problems with node failures. Networks22 (1992) 589–605.  Zbl0766.90031
  83. P. Jaillet, Analysis of probabilistic combinatorial optimization problems in Euclidean spaces. Math. Oper. Res.18 (1993) 51–70.  Zbl0777.90048
  84. P. Jaillet and A.R. Odoni, The probabilistic vehicle routing problem, in Vehicle routing: Methods and Studies, edited by B.L. Golden and A.A. Assad. North Holland, Amsterdam (1988) 293–318.  Zbl0653.90032
  85. P. Jaillet and M.R. Wagner, Online routing problems: Value of advanced information as improved competitive ratios. Transp. Sci.40(2006) 200–210.  
  86. D.S. Johnson, Near-optimal bin packing algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1973).  
  87. D.S. Johnson, Fast algorithms for bin packing. J. Comput. Syst. Sci.8 (1974) 272–314.  Zbl0284.68023
  88. D.S. Johnson and M.R. Garey, A 71/60 theorem for bin packing. J. Complex.1 (1985) 65–106.  Zbl0604.68046
  89. N. Karmarkar and R.M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, in FOCS, Chicago, IEEE Computer Society Illinois (1982) 312–320.  
  90. R.M. Karp, Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res.2 (1977) 209–224.  Zbl0391.90091
  91. R.M. Karp, A patching algorithm for the nonsymmetric traveling-salesman problem. SIAM J. Comput.8 (1979) 561.  Zbl0427.90064
  92. V. King, Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, in FOCS. IEEE Computer Society (1999) 81–91.  
  93. P.N. Klein and S. Subramanian, A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica22 (1998) 235–249.  Zbl0915.68130
  94. S.R. Kosaraju, J.K. Park and C. Stein, Long tours and short superstrings (preliminary version), in FOCS. IEEE Computer Society (1994) 166–177.  
  95. J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, in Proceedings of the American Mathematical Society7 (1956).  
  96. P.S. Loubal, A network evaluation procedure. Bay Area Transportation Study Commission (1967).  
  97. C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, in Proc. ICALP’93, Lecture Notes in Computer Science700. edited by A. Lingas, R.G. Karlsson and S. Carlsson. Springer-Verlag (1993) 40–51.  
  98. P.B. Miltersen, S. Subramanian, J.S. Vitter and R. Tamassia, Complexity models for incremental computation. Theor. Comput. Sci.130 (1994) 203–236.  Zbl0808.68061
  99. C. Murat and V.Th. Paschos, The probabilistic longest path problem. Networks33 (1999) 207–219.  Zbl0949.90013
  100. C. Murat and V.Th. Paschos, A priori optimization for the probabilistic maximum independent set problem. Theor. Comput. Sci.270 (2002) 561–590.  Zbl0988.68135
  101. C. Murat and V.Th. Paschos, The probabilistic minimum vertex-covering problem. Int. Trans. Oper. Res.9 (2002) 19–32.  Zbl0994.90122
  102. C. Murat and V. Paschos, The probabilistic minimum coloring problem, in Graph-Theoretic Concepts in Computer Science, Springer (2003) 346–357.  Zbl1255.68085
  103. C. Murat and V.T. Paschos, On the probabilistic minimum coloring and minimum k-coloring. Discrete Appl. Math.154 (2006) 564–586.  Zbl1087.05025
  104. C. Murat and V.T. Paschos, Probabilistic combinatorial optimization on graphs. Wiley Online Library (2006).  Zbl1119.90033
  105. 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).  
  106. C.H. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two. Math. Oper. Res.18 (1993) 1–11.  Zbl0778.90057
  107. A. Paz and S. Moran, Non deterministic polynomial optimization problems and their approximations. Theor. Comput. Sci.15 (1981) 251–277.  Zbl0459.68015
  108. K. Pruhs, E. Torng and J. Sgall, Online scheduling, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, edited by Joseph Y.-T. Leung, Chapter 15. CRC Press (2004) 15-1–15-41.  
  109. M.B. Richey, Improved bounds for harmonic-based bin-packing algorithms. Discrete Appl. Math.3 (1991) 203–227.  Zbl0768.68058
  110. N. Robertson and P.D. Seymour, Graph minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B92 (2004) 325–357.  Zbl1061.05088
  111. G. Robins and A. Zelikovsky, Improved steiner tree approximation in graphs, in SODA (2000) 770–779.  Zbl0957.68084
  112. V.V. Rodionov, The parametric problem of shortest distances. USSR Comput. Math. Math. Phys.8 (1968) 336–343.  Zbl0214.18901
  113. H. Rohnert, A dynamization of the all pairs least cost path problem, in STACS, Lecture Notes in Computer Science182, edited by K. Mehlhorn. Springer (1985) 279–286.  Zbl0568.68050
  114. S. Sahni and T.F. Gonzalez, P-complete approximation problems. J. ACM23 (1976) 555–565.  Zbl0348.90152
  115. M.W. Schäffter, Scheduling with forbidden sets. Discrete Appl. Math.72 (1997) 155–166.  Zbl0879.90118
  116. R. Seguin, Problèmes stochastiques de tournées de véhicules: un pas de plus vers le réalisme. Cahiers du Centre d’études de recherche opérationnelle35 (1993) 187–226.  
  117. J. Sgall, On-line scheduling-a survey, in Online Algorithms: The State of the Art, edited by A. Fiat and G.J. Woeginger, Lect. Notes Comput. Sci.1442. Springer (1998) 196–231. (1997).  
  118. R. Sitters, The minimum latency problem is np-hard for weighted trees, in IPCO, Lecture Notes in Computer Science2337, edited by W. Cook and A.S. Schulz. Springer (2002) 230–239.  Zbl1049.90531
  119. D.D. Sleator and R.E. Tarjan, A data structure for dynamic trees. J. Comput. Syst. Sci.26 (1983) 362–391.  Zbl0509.68058
  120. J.M. Steele, Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab.9 (1981) 365–376.  Zbl0461.60029
  121. J.M. Steele, On Frieze’s χ(3) limit for lengths of minimal spanning trees. Discrete Appl. Math.18 (1987) 99–103.  Zbl0621.05012
  122. Z. Sweedyk, A 2+1/2-approximation algorithm for shortest superstring. SIAM J. Comput.29 (1999) 954–986.  Zbl1051.68060
  123. A. Van Vliet, An improved lower bound for on-line bin-packing algorithms. Inf. Proc. Lett.43 (1992) 277–284.  Zbl0764.68083
  124. V. Vassilevska, Explicit inapproximability bounds for the shortest superstring problem, in MFCS, Lecture Notes in Computer Science3618, edited by J. Jedrzejowicz and A. Szepietowski. Springer (2005) 793–800.  Zbl1156.68394
  125. A. Wagner, On finite affine line transitive planes. Math. Zeitschr.87 (1965) 1–11.  Zbl0131.36804

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.