| DESIGN
OF HEURISTICS FOR THE SOLUTION OF COMPLEX PROBLEMS IN RESOURCE MANAGEMENT |
Optimization Problems and Basic Algorithmic Techniques
[1] A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The
Design and Analysis of Computer Algorithms, Addison-Wesley, Reading
MA, 1974.
[2] H.E. Ascher and H. Feingold, Repairable Systems Reliability: Modelling, Inference, Misconceptions and Their Causes, Marcel Dekker, New York, 1984.
[3] G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi, Toward a unified approach for the classification of NP-complete optimization problems, "Theoretical Computer Science", 12, 1980, pp. 83-96.
[4] B.S. Baker, A new proof for the first fit decreasing algorithm, Technical Report, Bell Laboratories, Murray Hill, 1983.
[5] J.L. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, vols. 1-2, Springer-Verlag, Berlin, 1988.
[6] R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, "J. Algorithms", 2, 1981, pp. 198-203.
[7] D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, 1994.
[8] E.G. Coffman Jr., M.R. Garey, and D.S. Johnson, Approximation algorithms for bin-packing - a survey, "in Approximation Algorithms for NP-hard Problems", PWS, Boston, 1997, pp. 46-93.
[9] S.A. Cook, The complexity of theorem-proving procedures, in "Proc. 3rd ACM Symposium on Theory of Computing", ACM, 1971, pp. 151-158.
[10] T. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.
[11] P. Crescenzi and R. Silvestri, Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems, "Information Processing Letters", 133, 1990, pp. 221-226.
[12] G.A. Croes, A method for solving traveling-salesman problems, "Operations Research", 6, 1958, pp. 791-812.
[13] S.E. Dreyfus and A.M. Law, The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.
[14] J. Edmonds, Matroids and the greedy algorithm, "Mathematical Programming", 1, 1971, pp. 127-136.
[15] M.R. Garey and D.S. Johnson, Strong NP-completeness results: motivation, examples, and implications, "J. ACM", 25, 1978, pp. 499-508.
[16] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[17] M.R. Garey and D.S. Johnson, Approximation algorithms for bin packing problems - a survey, in Analysis and Design of Algorithms in Combinatorial Optimization, Springer-Verlag, Berlin, 1981, pp. 147-172.
[18] M.X. Goemans and D.P. Williamson, The primal-dual method for approximation algorithms and its applications to network design problems, in Approximations Algorithms for NP-hard Problems, PWS, Boston, 1997, pp. 144-191.
[19] R.L. Graham, Bounds for certain multiprocessing anomalies, "Bell System Technical J.", 45, 1966, pp. 1563-1581.
[20] R.L. Graham, Bounds for multiprocessing timing anomalies, "SIAM J. Applied Mathematics", 17, 1969, pp. 263-269.
[21] R.L. Graham and P. Hell, On the history of the spanning tree problem, "IEEE Annals of the History of Computing", 7, 1985, pp. 8-23.
[22] M.M. Halldorsson and J. Radhakrishnan, Greed is good: approximating independent set in sparse and bounded degree graphs, in "Proc. 26th ACM Symposium on Theory of Computing", ACM, 1994, pp. 439-448.
[23] D.S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, "SIAM J. Computing", 11, 1982, pp. 555-556.
[24] D.S. Johnson, Near-optimal bin packing algorithms, Technical Report MAC TR-109, Project MAC, MIT, Cambridge, 1972.
[25] D.S. Johnson, Approximation algorithms for combinatorial problems, "J. Computer and System Sciences", 9, 1974, pp. 256-278.
[26] D.S. Johnson, Worst case behavior of graph coloring algorithms, in "5th Southeastern Conference on Combinatorics", Graph Theory and Computing, 1974, pp. 513-527.
[27] M. Junger, G. Reinelt, and G. Rinaldi, The traveling salesman problem, in Handbook on Operations Research and Management Sciences: Network Models, North-Holland, Amsterdam, 1994, pp. 225-330.
[28] R.M. Karp, Reducibility among combinatorial problems, in "Complexity of Computer Computations", Plenum Press, 1972, pp. 85-103.
[29] D.E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Addison-Wesley, Reading MA, 1969.
[30] D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley, Reading MA, 1971.
[31] D.E. Knuth, The Art of Computer Programming: Sorting and Searching, Addison-Wesley, Reading MA, 1973.
[32] B. Korte, L. Lovasz, and R. Schrader, Greedoids, Springer-Verlag, Berlin, 1991.
[33] M.W. Krentel, The complexity of optimization problems, "J. Computer and System Sciences", 36, 1988, pp. 490-509.
[34] L.A. Levin, Universal sorting problems, "Problems of Information Transmission", 9, 1973, pp. 265-266.
[35] S. Lin, Computer solutions for the traveling salesman problem, "Bell System Technical J.", 10, 1965, pp. 2245-2269.
[36] D.W. Matula and L.L. Beck, Smallest last ordering and clustering and graph coloring algorithms, "J. ACM", 30, 1983, pp. 417-427.
[37] D.W. Matula, G. Marble, and J.D. Isaacson, Graph coloring algorithm, in Graph Theory and Computing, Academic Press, New York, 1972, pp. 108-122.
[38] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995.
[39] C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading MA, 1994.
[40] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, 1982.
[41] A. Paz and S. Moran, Non deterministic polynomial optimization problems and their approximations, "Theoretical Computer Science", 15, 1981, pp. 251-277.
[42] G. Reinelt, The Traveling Salesman, Computational Solutions for TSP Applications, Lecture Notes in Computer Science 840, Springer-Verlag, Berlin, 1994.
[43] H. Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge MA, 1987.
[44] D.J. Rosenkrantz, R.E. Stearns, and P.M. Lewis, An analysis of several heuristics for the traveling salesman problem, "SIAM J. Computing", 6, 1977, pp. 563-581.
[45] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading MA, 1996.
[46] L.A. Wolsey, Heuristic analysis, linear programming and branch and bound, "Mathematical Programming Study", 13, 1980, pp. 121-134.
[2] H.E. Ascher and H. Feingold, Repairable Systems Reliability: Modelling, Inference, Misconceptions and Their Causes, Marcel Dekker, New York, 1984.
[3] G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi, Toward a unified approach for the classification of NP-complete optimization problems, "Theoretical Computer Science", 12, 1980, pp. 83-96.
[4] B.S. Baker, A new proof for the first fit decreasing algorithm, Technical Report, Bell Laboratories, Murray Hill, 1983.
[5] J.L. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, vols. 1-2, Springer-Verlag, Berlin, 1988.
[6] R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, "J. Algorithms", 2, 1981, pp. 198-203.
[7] D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, 1994.
[8] E.G. Coffman Jr., M.R. Garey, and D.S. Johnson, Approximation algorithms for bin-packing - a survey, "in Approximation Algorithms for NP-hard Problems", PWS, Boston, 1997, pp. 46-93.
[9] S.A. Cook, The complexity of theorem-proving procedures, in "Proc. 3rd ACM Symposium on Theory of Computing", ACM, 1971, pp. 151-158.
[10] T. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.
[11] P. Crescenzi and R. Silvestri, Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems, "Information Processing Letters", 133, 1990, pp. 221-226.
[12] G.A. Croes, A method for solving traveling-salesman problems, "Operations Research", 6, 1958, pp. 791-812.
[13] S.E. Dreyfus and A.M. Law, The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.
[14] J. Edmonds, Matroids and the greedy algorithm, "Mathematical Programming", 1, 1971, pp. 127-136.
[15] M.R. Garey and D.S. Johnson, Strong NP-completeness results: motivation, examples, and implications, "J. ACM", 25, 1978, pp. 499-508.
[16] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[17] M.R. Garey and D.S. Johnson, Approximation algorithms for bin packing problems - a survey, in Analysis and Design of Algorithms in Combinatorial Optimization, Springer-Verlag, Berlin, 1981, pp. 147-172.
[18] M.X. Goemans and D.P. Williamson, The primal-dual method for approximation algorithms and its applications to network design problems, in Approximations Algorithms for NP-hard Problems, PWS, Boston, 1997, pp. 144-191.
[19] R.L. Graham, Bounds for certain multiprocessing anomalies, "Bell System Technical J.", 45, 1966, pp. 1563-1581.
[20] R.L. Graham, Bounds for multiprocessing timing anomalies, "SIAM J. Applied Mathematics", 17, 1969, pp. 263-269.
[21] R.L. Graham and P. Hell, On the history of the spanning tree problem, "IEEE Annals of the History of Computing", 7, 1985, pp. 8-23.
[22] M.M. Halldorsson and J. Radhakrishnan, Greed is good: approximating independent set in sparse and bounded degree graphs, in "Proc. 26th ACM Symposium on Theory of Computing", ACM, 1994, pp. 439-448.
[23] D.S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, "SIAM J. Computing", 11, 1982, pp. 555-556.
[24] D.S. Johnson, Near-optimal bin packing algorithms, Technical Report MAC TR-109, Project MAC, MIT, Cambridge, 1972.
[25] D.S. Johnson, Approximation algorithms for combinatorial problems, "J. Computer and System Sciences", 9, 1974, pp. 256-278.
[26] D.S. Johnson, Worst case behavior of graph coloring algorithms, in "5th Southeastern Conference on Combinatorics", Graph Theory and Computing, 1974, pp. 513-527.
[27] M. Junger, G. Reinelt, and G. Rinaldi, The traveling salesman problem, in Handbook on Operations Research and Management Sciences: Network Models, North-Holland, Amsterdam, 1994, pp. 225-330.
[28] R.M. Karp, Reducibility among combinatorial problems, in "Complexity of Computer Computations", Plenum Press, 1972, pp. 85-103.
[29] D.E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Addison-Wesley, Reading MA, 1969.
[30] D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley, Reading MA, 1971.
[31] D.E. Knuth, The Art of Computer Programming: Sorting and Searching, Addison-Wesley, Reading MA, 1973.
[32] B. Korte, L. Lovasz, and R. Schrader, Greedoids, Springer-Verlag, Berlin, 1991.
[33] M.W. Krentel, The complexity of optimization problems, "J. Computer and System Sciences", 36, 1988, pp. 490-509.
[34] L.A. Levin, Universal sorting problems, "Problems of Information Transmission", 9, 1973, pp. 265-266.
[35] S. Lin, Computer solutions for the traveling salesman problem, "Bell System Technical J.", 10, 1965, pp. 2245-2269.
[36] D.W. Matula and L.L. Beck, Smallest last ordering and clustering and graph coloring algorithms, "J. ACM", 30, 1983, pp. 417-427.
[37] D.W. Matula, G. Marble, and J.D. Isaacson, Graph coloring algorithm, in Graph Theory and Computing, Academic Press, New York, 1972, pp. 108-122.
[38] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995.
[39] C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading MA, 1994.
[40] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, 1982.
[41] A. Paz and S. Moran, Non deterministic polynomial optimization problems and their approximations, "Theoretical Computer Science", 15, 1981, pp. 251-277.
[42] G. Reinelt, The Traveling Salesman, Computational Solutions for TSP Applications, Lecture Notes in Computer Science 840, Springer-Verlag, Berlin, 1994.
[43] H. Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge MA, 1987.
[44] D.J. Rosenkrantz, R.E. Stearns, and P.M. Lewis, An analysis of several heuristics for the traveling salesman problem, "SIAM J. Computing", 6, 1977, pp. 563-581.
[45] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading MA, 1996.
[46] L.A. Wolsey, Heuristic analysis, linear programming and branch and bound, "Mathematical Programming Study", 13, 1980, pp. 121-134.
