**S. Thomas (Tom)
McCormick**

AB (Penn), PhD (Stanford)

WJ Van Dusen Professor in Management

Professor, Operations and Logistics Division

**Contact
Information**

Office: Henry Angus 463

Tel: (604) 822-8426

Fax: (604) 822-9574

Email: __Tom.McCormick
[at-sign] sauder [dot] ubc [dot] ca__

**Research Interests**

My research looks at
optimizing mathematical models of business processes. I am particularly interested in models of
flows of various commodities through networks, and problems of scheduling. I am also interested in problems where
submodularity and/or parametric optimization come into play. Some of this work is around computational
complexity: which problems are NP Hard, and which are computationally
tractable? When a problem is tractable,
what is the fastest algorithm for it?
Lately I have been interested in some real-world problems in supply
chains and block cave mining.

**Teaching Interests**

I have taught at many
levels: undergraduate, masters, PhD, executive programs, and in both
engineering and business schools. I have
given short courses in optimization in

**Publications**

[1] P. Pesneau,
B. Fortz, A.R. Mahjoub, and S. T. McCormick (2006). The 2-Edge Connected

Subgraph Problem with Bounded Rings. Math. Prog., 105, 85111.

[2] S. Iwata, S. T.
McCormick, and M. Shigeno (2005). A Strongly Polynomial Cut Canceling
Algorithm for the Submodular Flow Problem. SIAM J. on Discrete
Math., 19, 304320; a preliminary
version appeared in Proceedings of the Seventh MPS Conference on Integer Programming and
Combinatorial Optimization (1999), G. Cornu΄ejols, R. E. Burkard, and G. J. Woeginger,
eds., 259272.

[3] S. Iwata, S. T.
McCormick, and M. Shigeno (2003). Fast Cycle Canceling Algorithms for
Minimum Cost Submodular Flow. Combinatorica 23, 503525; an extended
abstract of a preliminary version appears as A Faster Algorithm for Minimum
Cost Submodular Flows Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete
Algorithms (1998),
167174.

[4] S.T.
McCormick, G. Rinaldi, and M.R. Rao
(2003). Easy and Difficult Objective Functions for Max Cut. Math. Prog. B, 94, 459466.

[5] Lisa K. Fleischer, S.
Iwata, and S. T. McCormick (2002). A
Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow. Math. Prog., 92, 119139.

[6] S.T. McCormick, S.R.
Smallwood and F.C.R. Spieksma (2001).A Polynomial Algorithm for Multiprocessor
Scheduling with Two Job Lengths. Math. of OR, 26, 3149. An extended
abstract appears in Proceedings of Eighth SODA (1997), 509517.

[7] S. Iwata, S. T.
McCormick, and M. Shigeno (2000). A Fast Cost Scaling Algorithm for Submodular Flow. Information Processing
Letters, 74, 123128.

[8] M. Shigeno, S. Iwata, and S.T. McCormick (2000).Relaxed
most negative cycle and most positive cut canceling algorithms for minimum cost
flow. Math.
of OR, 25, 76104.

[9] S.T. McCormick and A. Shioura
(2000). Minimum Ratio Canceling is Oracle Polynomial
for Linear Programming, but Not Strongly Polynomial, Even for Networks. OR Letters, 27, 199 207. An extended
abstract appeared in Proceeding of SODA 2000, 944952.

[10] S.T. McCormick
(1995).A Polynomial Algorithm for
Abstract Maximum Flow. An extended abstract
appears in Proceedings
of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 490497.

[11] McCormick, S.T.
(2000).Fast Algorithms for Parametric Scheduling come
from Extensions to Parametric Maximum Flow. Operations Research, 47, 744756; an extended
abstract appears in Proceedings of Symposium on the Theory of Computing (1996) 319 328.

[12] S. Iwata, T. Matsui,
and S.T. McCormick (1998). A Fast
Bipartite Network Flow Algorithm for Selective Assembly. OR Letters, 22, 137143.

[13] S.T. McCormick
(1997). How to Compute Least Infeasible Flows. Math Programming B, 78, 179194. An extended
abstract appears in the program book of NETFLOW93, 160164.

[14]
A.V. Karzanov and S.T. McCormick (1997).Polynomial
Methods for Separable Convex Optimization in Totally Unimodular
Linear Spaces with Applications to Circulations and Cocirculations
in Networks.

[15] S.T. McCormick (1996).
Submodular Containment is Hard, Even for Networks.
OR Letters, 19, 9599.

[16] S.T. McCormick and
M.L. Pinedo (1995). Scheduling
n Independent
Jobs on m Uniform
Machines with both Flow Time and Makespan Objectives:
A Parametric Approach. ORSA Journal on Computing, 7, 6377.

[17] S.T. McCormick and

[18] S.T. McCormick and
T.R. Ervolina (1994). Computing
Maximum Mean Cuts. Discrete Applied Math, 52, 5370.

[19] T.R. Ervolina and S.T. McCormick (1993). Two Strongly Polynomial Cut Cancelling Algorithms for Minimum Cost
Network Flow. Discrete Applied Math, 46, pp. 133165.

[20] S.T. McCormick
(1993). Approximate Binary Search Algorithms for Mean
Cuts and Cycles. OR Letters, 14, 129132.

[21] T.R. Ervolina and S.T. McCormick (1993). Cancelling
Most Helpful Total Cuts for Minimum Cost Network Flow. Networks, 23, pp. 4152.

[22] S.F. Chang and S.T.
McCormick (1993). Computational
Results for the Hierarchical Algorithm for Making Sparse Matrices Sparser. ACM Transactions on Mathematical Software, 19, 419441.

[23] S.T. McCormick and
S.F. Chang (1993). The Weighted Sparsity
Problem: Complexity and Algorithms.

[24] S.F. Chang and S.T.
McCormick (1992). A Hierarchical
Algorithm for Making Sparse Matrices Sparser.
Mathematical
Programming, 56, pp. 130.

[25] C-L. Li, S.T.
McCormick and D. Simchi-Levi (1992). On the Minimum-Cardinality-Bounded- Diameter and the
Fixed-Budget-Minimum-Diameter Edge Addition Problems. OR Letters, 11, pp. 303308.

[26] C-L. Li, S.T.
McCormick and D. Simchi-Levi (1992). Finding Disjoint
Paths with Different Path Costs: Complexity and Algorithms. Networks, 22, pp. 653667.

[27] C-L. Li, S.T. McCormick and D. Simchi-Levi (1992). The Point-to-Point Delivery and Connection Problems: Complexity and Algorithms. Discrete Applied Mathematics, 36, pp. 267292. [the pdf file is missing the lines in the figures, but they should be clear from the text]

[28] D.L. Applegate, W.J.
Cook and S.T. McCormick (1991). Integral Infeasibility and Testing Total Dual Integrality. OR Letters, 10,
pp. 3741.

[29] S.T. McCormick, M.L. Pinedo, S. Shenker and B. Wolf
(1991). Transient Behavior in a Flexible Assembly System, International Journal of
Flexible Manufacturing Systems, 3, pp. 2744.

[30] S.T. McCormick
(1990). Making Sparse
Matrices Sparser: Computational Results. Math. Programming, 49, pp. 91111.

[31] C-L. Li, S.T.
McCormick and D. Simchi-Levi (1990). The Complexity of Finding Two Disjoint
Paths with Min-Max Objective Function, Discrete Applied Mathematics, 26, pp. 105115.

[32] S.T. McCormick, M.L. Pinedo, S. Shenker and B. Wolf
(1989). Sequencing
in an Assembly Line with Blocking to Minimize Cycle Time, Operations
Research, 37,
pp. 925935.

[33] S.S. Chaudhry, S.T. McCormick and J.D. Moon (1987). Conditional
Covering: Greedy Heuristics and Computational Results, Computers in Operations Research,
14, pp. 1118.

[34] S.S. Chaudhry, S.T. McCormick and J.D. Moon (1986). Locating
Independent Facilities with Maximum Weight: Greedy Heuristics, OMEGA, 14, pp. 383389.

[35] S.T. McCormick
(1983). Optimal
Approximation of Sparse Hessians and its Equivalence to a Graph Coloring
Problem. Mathematical Programming, 26, pp. 153171.

**Articles Submitted to Refereed Journals**

[36] F.
Granot, S.T. McCormick, M.N. Queyranne, and F. Tardella (2008). Monotone
parametric min cut revisited: structures and algorithms. Submitted to Math. of OR.

[37] S.
T. McCormick and S. Fujishige (2008). Strongly
Polynomial and Fully Combinatorial Algorithms for Bisubmodular Function
Minimization. Revision submitted to Mathematical Programming.

[38] Maren
Martens, S. T. McCormick, and Maurice Queyranne (2008). Separation, Dimension, and Facet Algorithms

for Node Flow Polyhedra. Submitted to SODA.

[39]
Jing Shao, Harish Krishnan, and S. T. McCormick (2008). Distributing
a Product Line in a Decentralized Supply

Chain. Submitted to POMS.

**Other Refereed Contributions**

[40]
S.T. McCormick and L. Liu (1993). An Experimental
Implementation of the Dual Cancel and Tighten Algorithm for Minimum Cost
Network Flow. In Network Flows and Matching, D.S. Johnson and C.S McGeoch,
eds., American Mathematical Society DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, Volume 12, 247266.

[41]
S.T. McCormick, M.L. Pinedo and B. Wolf (1986). Sequencing in a Flexible
Assembly Line with Blocking to Minimize Cycle Time. In Flexible Manufacturing
Systems, K.E.
Stecke and R. Suri, eds.,
Elsevier,

[42]
Alan J. Hoffman and S.T. McCormick (1984). A Fast Algorithm that Makes Matrices
Optimally Sparse. In Progress in Combinatorial Optimization, W. Pulleyblank, ed., Academic Press,

**Book Chapters**

The following book chapter was published by Elsevier
as part of the *Handbook on Discrete
Optimization*, and contains lots of good stuff. I encourage you to buy the handbook at the
following link:

www.elsevier.com/wps/find/bookdescription.cws_home/699541/description#description

However, since publication there have been exciting
new developments in Submodular Function Minimization, such as Orlins
Algorithm. The link below is to an
updated version (now Version 3a, updated 11 February 2008) which clarifies SFM
on ring families, and updates the section on computational results.

S. T. McCormick (2006). Submodular Function Minimization. Chapter 7 in the
Handbook on

Discrete Optimization,
Elsevier, K. Aardal, G. Nemhauser, and R. Weismantel, eds,
321391.

S. T. McCormick (1999).
Minimum Cost Single Commodity Flow. Chapter 9.4 in the

Handbook of Applied
Optimization,

eds.

Last updated: 4 July 2008