COMBINATORIAL OPTIMIZATION

Some Basic Problems

1. Knapsack problem
2. Assignment problem
3. Scheduling Problems (e.g, ordering, sequencing)
4. Packing problems
5. Bin-packing problem
6. Traveling salesman problem
7. Assignment, location, allocation problems
8. The stable marriage problem
9. Covering problems
10. Routing / Flow Problems
11. The maximum clique problem, weighted clique in multipartite graph, multipartite graph clustering, morphological clique
12. Independent set problem
13. Clustering problems
14. Spanning tree problems
15. Minimal Steiner tree problems
16. Allignment problems
17. Matching problems
18. Graph coloring
19. Timetabling problems

Research Groups and Centers

  • Combinatorial Optimization Group, Eindhoven Univ. of Technology
  • Combinatorics Group at Oxford University
  • Centre for Discrete and Applicable Mathematics (London School of Economics)
  • CADCOM: Committee for the Advancement of Discrete and Combinatorial Mathematics
  • Automated Scheduling and Planning Group (Univ. of Nottingen)
  • Working Group on Automating Time Tabling (Europe)
  • Special Interest Group for Cutting and Planning
  • Steven S. Skiena (Dept. of CS, State Univ. of New York)
  • Martin Croetschel (Inst. for Mathematics, TU Berlin)
  • Center for Algorithm Engineering (Prof. Michael T. Goodrich, CS Dept., Johns Hopkins Univ.)
  • Algorithm Engineering Group (Dept. of Computer and System Sci., Univ. of Roma)
  • Andrew V. Goldberg and Andrew Goldberg's Network Optimization Library
  • Research Group on Algorithm Engineering (CS & Software Eng. Dept., Univ. of Canterbury)
  • Centre for Discrete Mathematics and Its Applications (DIMAP) (Dept. of CS & Warwick Mathematics Inst., Univ. of Warwick)
  • Concordia Computational Combinatorial Optimization Laboratory ConCoCO (Prof. Vasek Chvatal et al., CS and Software Engineering, Faculty of Engineering and CS, Concordia Univ., CA)
  • Center for Discrete Mathematics & Theoretical Computer Science (DIMACS) (New Jersey, USA)

    Journals

  • Journal of Heuristcs
  • Journal of Combinatorial Optimization
  • Operations Research
  • Eur. Journal of Operational Research
  • Journal of the Operational Research Society
  • Mathematics of Operations Research
  • Computers and Operations Research
  • Location Science
  • Algorithmica
  • SIAM J. on Discrete Mathematics
  • SIAM J. on Computing
  • Applied Discrete Mathematics
  • Discrete Mathematics
  • Orders
  • INFOR
  • Networks
  • Naval Research Logistics
  • Operations Research Letters
  • Information Research Letters
  • Journal of Global Optimization
  • Journal of Algorithms
  • Omega
  • Information Processing Letters
  • Operations Research Letters
  • International Transactions in Operational Research
  • Journal of Scheduling
  • Constraints

    Bibliography

  • Some Basic papers
    1. S.M. Johnson, Optimal Two-and-Three-Stage Production Schedules. Naval Res. Logist. Quart.,
    1(1), 61-68, 1954.
    2. R.M. Karp, Combinatorics, Complexity, and Randomness. Comm. of the ACM, 29/2, 98-109, 1986.

  • Books
    1. M.R. Garey, and D.S. Johnson, Computers and Intractability. The Guide to the Theory of NP-Completeness.
    San-Francisco: W.H. Freeman and Company, 1979.
    2. F.R. Roberts, Applied Combinatorics, NJ: Prentice Hall, Englewood Cliffs, 1984.
    3. C.H. Papadimitriou, and K. Steiglitz, Combinatorial Optimization. NJ: Prentice Hall, Englewood Cliffs, 1982.
    4. G.L. Nemhauser, and L.A. Wolsey, Integer and Combinatorial Optimization. New York: J.Wiley & Sons, 1988.
    5. E.M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms. NJ: Prentice Hall, Englewood Cliffs, 1977.
    6. E.G. Coffman, Jr. (ed.), Scheduling in Cmputer and Job Shop Systems, New York: J.Wiley & Sons, 1976.
    7. G. Reinelt, The Traveling Salesman, Berlin: Springer-Verlag, 1994.
    8. J. Aoe, (ed.), Computer Algorithms: String Pattern Matching Strategies. Los Alamitos: IEEE CS Press, 1994.
    9. J. Blazewicz, K.H. Ecker, G. Schmidt, and J. Weglarz, Scheduling in Computer and Manufacturing Systems, 2nd ed., Berlin: Springer-Verlag, 1994.
    10. M.S. Daskin, Networks and Discrete Location. Models, Algorithms, and Applications. New York: J.Wiley & Sons, 1976.
    11. P.B. Mirchandani, and R.L. Francis, (Eds.) Discrete Location Theory, New York: J.Wiley & Sons, 1990.
    12. E. Minieka, Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker, 1978.
    13. S. Martello, and P. Toth, Knapsack Problem: Algorithms and Computer Implementation. New York: J.Wiley & Sons, 1990.
    14. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, (eds.), The Traveling Salesman Problem. Chichester: J.WIley & Sons, 1985.
    15. T.R. Jensen, and B. Toft, Graph Coloring Problems. New York: J.Wiley & Sons, 1990.
    16. D.S. Johnson, and M.A. Trick, (Eds.), Cliques, Coloring, and Satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, Providence: AMS, 1996.
    17. F. Harary, R.Z. Norman, and D. Carthwright, Structural Models: An Introduction to the Theory of Directed Graphs. New York: J.Wiley & Sons, 1965.
    18. M. Hall, Jr., Combinatorial Theory, 2nd ed., New York: J.Wiley & Sons, 1986.
    19. D. Gusfield, and R.W. Irving, The Stable Marriage Problem: Structure and Algorithms, Boston: The MIT Press, 1989.
    20. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.
    21. J. Blazewicz, W. Cellary, R. Slowinski, and J. Weglarz, Scheduling under Resource Constraints: Deterministic Models. Basel: Baltzer, 1986.
    22. E. Cela, The Quadratic Assignment Problem: Theory and Algorithms. Dordrecht: Kluwer, 1997.
    23. A.I. Barros, Discrete and Fractional Programming Techniques for Location Models. Dordrecht: Kluwer, 1998.
    24. R.W. Conway, W.L. Maxwell, and L.W. Miller, Theory of scheduling. Mass.: Addison-Wesley, Reading, 1967.
    25. K. Baker, Introduction to Sequencing and Scheduling. New York: J.Wiley and Sons, 1974.
    26. B.I. Goldengorin, Requiremments of Standards: Optimization Models and Algorithms. Hoogezand, The Netherlands: Operations Research Co., 1995.
    27. S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. New York: J.Wiley and Sons, 1982.
    28. J. Lee, First Course in Combinatorial Optimization. Cambridge Univ. Press, New York, 2004.
    29. R.Y. Rubenstein, D.P. Kroese, The Cross Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. Springer, 2004.
    30. Gang Yu, (Ed.) Industrial Applications of Combinatorial Optimization. Dordrecht: Kluwer, Hardbound, ISBN 0-7923-5073-1, June 1998
    31. D.J.A. Welsh, (Ed.) Combinatorial Mathematics and Its Applications. New York: Academic Press, 1971
    32. M.Crochemore, W. Rytter, Jewels of Stringology. World Scientific, 2002.
    33. D.L. Applegate, R.E. Bixby, V. Chvatal, W.J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton Univ. Press, 2007.

    Information Resources

  • Combinatorial Catalogues
  • Combinatorial Problems: Formulations, Algorithms
  • Algorithm Page
  • Genetic Algorithm Archive
  • On-line Bibliography on Planning and Scheduling
  • Packing Bibliography
  • Quadratic Assignment Problem Library
  • ALgorithms and COMplexity in Information Technology EU ESPRIT Project
  • QAPLIB - A Quadratic Assignment Problem Library (R.E. Burkard, E. Cela, S.E. Karish, & F. Rendl)
  • Dictionary of Algorithms and Data Structures (Paul E. Black)
  • Operations Research Models and Methods INTERNET (by Paul O. Jensen)
  • OR-Library by J.E. Beasley
  • Mathematical Programming Glossary by Harvey J. Greenberg
  • TSPBIB Home Page (Pablo Moscato)
  • Classification and Clustering: Boris G. Mirkin (Birkbeck College)
  • Andrew Goldberg's Network Optimization Library

    Polyhedra

  • Tom Gettys' Polyhedra Hyperpages
  • George W. Hart's Virtual Reality Polyhedra page
  • Fr. Magnus Wenninger--Polyhedron Constructions
  • Approximation Algorithms (Uri Zwick, Tel Aviv Univ., Israel)
  • Electronic Colloquium on Computational Complexity - Research reports, surveys and books in computational complexity (Univ. of Trir, Germany)