S. Thomas McCormick
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
S. Thomas McCormick has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Maurice Queyranne
Sauder School of Business at the University of British Columbia
4 shared publications - Hassene Aissi
Paris Dauphine University
3 shared publications - Ali Ridha Mahjoub
Université Paris-Dauphine, Paris, France
2 shared publications - Britta Peis
RWTH Aachen, Aachen, Germany
2 shared publications - Britta Peis
RWTH Aachen University, Aachen, Germany
2 shared publications - Gianpaolo Oriolo
DICII University of Rome Tor Vergata Italy
2 shared publications
Latest Publications
- Open Access
Complexity of Source-Sink Monotone 2-Parameter Min Cut
There are many applications of max flow with capacities that depend on one or more parameters. Many of these applications fall into the "Source-Sink Monotone" framework, a special case of Topkis's monotonic optimization framework, which implies that the parametric min cuts are nested. When there is a single parameter, this property implies that the number of distinct min cuts is linear in the number of nodes, which is quite useful for constructing algorithms to identify all possible min cuts. When there are multiple Source-Sink Monotone parameters and the vector of parameters are ordered in the usual vector sense, the resulting min cuts are still nested. However, the number of distinct min cuts was an open question. We show that even with only two parameters, the number of distinct min cuts can be exponential in the number of nodes.
Open AccessComplexity of Source-Sink Monotone 2-Parameter Min Cut
There are many applications of max flow with capacities that depend on one or more parameters. Many of these applications fall into the "Source-Sink Monotone" framework, a special case of Topkis's monotonic optimization framework, which implies that the parametric min cuts are nested. When there is a single parameter, this property implies that the number of distinct min cuts is linear in the number of nodes, which is quite useful for constructing algorithms to identify all possible min cuts. When there are multiple Source-Sink Monotone parameters and the vector of parameters are ordered in the usual vector sense, the resulting min cuts are still nested. However, the number of distinct min cuts was an open question. We show that even with only two parameters, the number of distinct min cuts can be exponential in the number of nodes.
- Open Access
- 1 January 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (1) , 84-90
Complexity of Source-Sink Monotone 2-parameter min cut
- 1 January 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (1) , 84-90
Open AccessComplexity of Source-Sink Monotone 2-parameter min cut
- 1 July 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (4) , 1256-1281
A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards
When allocating scarce resources such as organs or public housing units, the policy maker needs to carefully balance two conflicting objectives: maximizing the reward from matching and minimizing inequity across different types of candidates. We consider an implementable class of policies that ranks the candidates by the sum of their waiting score and matching score. Similar policies had been proposed for allocating deceased-donor kidneys to patients on the transplant waitlist. This article provides a modeling framework to characterize the waitlist system under this type of ranking policy. This framework allows the policy maker to predict and compare the allocation outcome under different ranking policies. When the efficiency and fairness measurements take certain forms, we derive a closed-form scoring formula that optimizes the outcome of the system in the long run.
- 1 July 2021
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 69 (4) , 1256-1281
A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards
When allocating scarce resources such as organs or public housing units, the policy maker needs to carefully balance two conflicting objectives: maximizing the reward from matching and minimizing inequity across different types of candidates. We consider an implementable class of policies that ranks the candidates by the sum of their waiting score and matching score. Similar policies had been proposed for allocating deceased-donor kidneys to patients on the transplant waitlist. This article provides a modeling framework to characterize the waitlist system under this type of ranking policy. This framework allows the policy maker to predict and compare the allocation outcome under different ranking policies. When the efficiency and fairness measurements take certain forms, we derive a closed-form scoring formula that optimizes the outcome of the system in the long run.
- Open Access
A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e. a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.
Open AccessA polynomial time algorithm for solving the closest vector problem in zonotopal lattices
In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e. a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.
- Open Access
- 14 April 2020
- Published by Springer Nature
- p. 27-39
Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts
- 14 April 2020
- Published by Springer Nature
- p. 27-39
Open AccessFaster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts
- Open Access
Faster Algorithms for Parametric Global Minimum Cut Problems
The parametric global minimum cut problem concerns a graph $G = (V,E)$ where the cost of each edge is an affine function of a parameter $\mu \in \mathbb{R}^d$ for some fixed dimension $d$. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.Open AccessFaster Algorithms for Parametric Global Minimum Cut Problems
The parametric global minimum cut problem concerns a graph $G = (V,E)$ where the cost of each edge is an affine function of a parameter $\mu \in \mathbb{R}^d$ for some fixed dimension $d$. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem. - 1 January 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 67 (1) , 163-166
Technical Note—Error Noted in “Order-Based Cost Optimization in Assemble-to-Order Systems” by Lu and Song (2005)
Discrete convexity, which extends submodularity to integer vectors, has been used in the economics and management literature to characterize the behavior of optimal policies. One of its variants, called L♮-convexity, has enabled recent advances in various operations management systems. In a paper published by Operations Research in 2005, an assemble-to-order inventory system was shown to have the L♮-convexity property, which was used to motivate an efficient algorithm. In a technical note, “Error Noted in ‘Order-Based Cost Optimization in Assemble-to-Order Systems’ by Lu and Song (2005)” by Bolandnazar, Huh, McCormick, and Murota, the authors show that the proof in that paper is incorrect and L♮-convexity may not hold. Despite this error, the authors credit Lu and Song for introducing this useful concept to the operations management community.
- 1 January 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 67 (1) , 163-166
Technical Note—Error Noted in “Order-Based Cost Optimization in Assemble-to-Order Systems” by Lu and Song (2005)
Discrete convexity, which extends submodularity to integer vectors, has been used in the economics and management literature to characterize the behavior of optimal policies. One of its variants, called L♮-convexity, has enabled recent advances in various operations management systems. In a paper published by Operations Research in 2005, an assemble-to-order inventory system was shown to have the L♮-convexity property, which was used to motivate an efficient algorithm. In a technical note, “Error Noted in ‘Order-Based Cost Optimization in Assemble-to-Order Systems’ by Lu and Song (2005)” by Bolandnazar, Huh, McCormick, and Murota, the authors show that the proof in that paper is incorrect and L♮-convexity may not hold. Despite this error, the authors credit Lu and Song for introducing this useful concept to the operations management community.
- 7 April 2017
- Published by Springer Nature in Mathematical Programming
- Vol. 169 (2) , 417-446
Matroid optimisation problems with nested non-linear monomials in the objective function
- 7 April 2017
- Published by Springer Nature in Mathematical Programming
- Vol. 169 (2) , 417-446
Matroid optimisation problems with nested non-linear monomials in the objective function
- 1 January 2017
- Published by Elsevier in Operations Research Letters
- Vol. 45 (1) , 53-59
Protection of flows under targeted attacks
- 1 January 2017
- Published by Elsevier in Operations Research Letters
- Vol. 45 (1) , 53-59
Protection of flows under targeted attacks