PUBLICATIONS (links are to pre-publication versions, slides, or secured published versions. To access the latter for educational purposes, send me email.)

Tovey, C. A., Fire in Summer, a 40-bar strathspey for two couples, in The First San Francisco Collection , RSCDS, San Francisco, 1980.

Tovey, C. A. and D. West, Semiantichains and Unichain Coverings in Direct Products of Partial Orders, SIAM J. Alg. Disc. Meth. , Vol. 2, No. 3, pp. 295-305, September 1981. Summary: partial result on a conjectured generalization of the Greene-Kleitman k-family generalization of Dilworth's Theorem. The conjecture is still open.

Tovey, C. A., On the Number of Iterations of Local Improvement Algorithms, Operations Research Letters , Vol. 2, No. 5, pp. 231-238, 1983.

Tovey, C. A., A Simplified NP-Complete Satisfiability Problem, Discrete Applied Mathematics , Vol. 8, No. 1, pp. 85-90, 1984. Summary: 3-SAT is easy if each variable appears in at most 3 clauses (3,3-SAT) (no repeats in a clause); hard if in 4 (3,4-SAT).

Tovey, C. A., Hill Climbing with Multiple Local Optima, SIAM J. Alg. Disc. Meth. , Vol. 6, No. 3, pp. 384-393, 1985. Summary: local search on binary variables takes O(n), O(n log n), O(n^2 log n), etc. steps on average under different probabilistic models of instances.

Tovey, C. A. and D. West, A Network Approach to Duality Theorems in the Product of Partial Orders, ORDER , Vol. 2, pp. 49-60, 1985. Summary: another partial result on the partial order product conjecture.

Tovey, C. A., Multiple Occurrences of Binomial Coefficients, The Fibonacci Quarterly , Vol. 23, pp. 356-358, October 1985.

Lofgren, C. and C. Tovey, Performance Bounds on Machine Configuration in Flexible Manufacturing Systems, MHRC Technical Report, Georgia Institute of Technology, Atlanta, Georgia, October 1985.

Tovey, C. A., Low Order Polynomial Bounds on the Expected Performance of Local Improvement Algorithms, Mathematical Programming , Vol. 35, No. 2, pp. 193-224, 1986. Summary: local search algorithms take O(n log n), O(n^2 log n) on average on problems with a single local optimum, under different models of random instances.

Tardos, E., C. Tovey, and M. Trick, Layered Augmenting Path Algorithms, Mathematics of Operations Research , Vol. 11, No. 2, pp. 362-370, 1986. Summary: speeds up the algorithms by Lawler and Martel for max polymatriodal flow, Franck for Edmonds-Giles polyhedron, Cunningham for matroid polyhedron membership, and Schonsleben for polymatroid intersection.

Fathi, Y. and C. Tovey, Affirmative Action Algorithms, Mathematical Programming , Vol. 34, No. 3, pp. 292-301, 1986.

Tovey, C. A., Rescheduling to Minimize Makespan on a Changing Number of Processors, Naval Research Logistics Quarterly , Vol. 33, pp. 717-724, 1986. Summary: LPT is more robust than any optimum schedule; rescheduling is formally difficult (NP-hard).

Rodl, V. and C. Tovey, Multiple Local Optima in Neighborhood Search, Journal of Algorithms , Vol. 8, pp. 250-259, 1987.

Tovey, C. A., G. Weiss, and J. Wilson, Minimum Spillage Sequencing, Management Science , Vol. 34, pp. 306-330, 1988.

Llewellyn, D. C., C. Tovey, and M. Trick, Finding Saddlepoints of Two-Person Zero-Sum Games, The American Mathematical Monthly , Vol. 95, pp. 912-918, 1988. Summary: first sub-quadratic algorithm, but a linear time algorithm was found later.

Tovey, C. A., Simulated Simulated Annealing, Journal of Mathematics and Management Sciences , Vol. 8, pp. 389-407, 1988. Summary: swindling tricks to speed up simulated annealing.

Bartholdi, J. J., C. Tovey, and M. Trick, The Computational Difficulty of Manipulating an Election, Social Choice and Welfare , Vol. 6, pp. 227-241, 1989. Summary: 1st use of complexity to circumvent strategic voting -- Gibbard-Satterthwaite and Gardenfors impossibility theorems.

Bartholdi, J. J., C. Tovey, and M. Trick, Voting Schemes for Which It Can be Difficult to Tell Who Won the Election, Social Choice and Welfare , Vol. 6, pp. 157-165, 1989. Summary: Dodgson and Kemeny (-Snell) voting procedures are NP-hard to compute.

Llewellyn, D. C., C. Tovey, and M. Trick, Local Optimization on Graphs, Discrete Applied Mathematics , Vol. 3, pp. 157-178, 1989. Summary: develops general theory of upper and lower bounds on cost of finding a local optimum.

Tovey, C. A., A Simplified Anomaly and Reduction for Multiprocessor Scheduling, SIAM Journal of Discrete Mathematics , Vol. 3, pp. 582-584, 1990. Summary: Shrinks Graham's classic anomaly for P|prec|p_j=1|C_max in which no list schedule is optimal for both m=2 and m+1=3 processors. Simpler anomaly for m>2, simple proof that the (unit time precedence constraint) problem is NP-complete even for makespan 3, and no precedence chain of edge length 2.

Stone, R. and C. Tovey, The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods, SIAM Review , Vol. 33, pp. 220-237, 1991.

Lofgren, C., L. McGinnis, and C. Tovey, Routing Printed Circuit Cards Through an Assembly Cell, Operations Research , Vol. 39, pp. 992-1004, 1991.

Borie, R. B., R.G. Parker, and C.A. Tovey, Automatic Generation of Linear Algorithms on Recursive Graphs From a Predicate Calculus, Algorithmica , Vol. 7, pp. 555-581, 1992.

Carter, M. and C. Tovey, When Is the Classroom Assignment Problem Hard?” Operations Research, Vol. 40, pp. 528-539, 1992.

Borie, R. B., R.G. Parker, and C.A. Tovey, Algorithms for Recognition of Regular Properties and Decomposition of Recursive Graph Families, Annals of Operations Research , Vol. 33, pp. 127-149, 1991. (Also in Proc. NATO Symposium on Networks ).

Bartholdi, J., C.A. Tovey, and M. Trick, How Hard Is It To Control an Election?, Mathematical and Computer Modelling , 1992.

Bartholdi, J., L. Narasimhan, and C. Tovey, Recognizing Majority-rule Equilibrium in Spatial Voting Models, Social Choice and Welfare , Vol. 8, pp. 183-197, 1991.

Bartholdi, J., T. Seeley, C. Tovey, and J. Vande Vate, The Pattern and Effectiveness of Forager Allocation Among Food Sources in Honey Bee Colonies, Journal of Theoretical Biology , Vol. 160, pp. 23-40, 1993.

Stone, R. and C. Tovey, Limiting Median Lines Do Not Suffice to Determine the Yolk, Social Choice and Welfare , Vol. 9, pp. 33-35, 1992.

Castanets, Carlitos (pseud.), Towards a Drug-Free Civilization, Journal of Irreproducible Results , 1992.

Borie, R. B., R.G. Parker, and C.A. Tovey, Deterministic Decomposition of Recursive Graph Classes, SIAM Journal of Discrete Mathematics , Vol. 4, pp. 481-501, 1991.

Dell, R., W. Kemple, and C. Tovey, Stratigraphic Correlation Based on Fossil Dating, 1st IE Research Conference, Chicago, Illinois 1992.

Llewellyn, D. C. and C.A. Tovey, Dividing and Conquering the Square, Discrete Applied Mathematics , Vol. 42, 1993.

Tovey, C. A., The Probability of an Undominated Central Voter in 2-dimensional Spatial Majority Voting, Social Choice and Welfare , Vol. 9, pp. 43-48, 1992. Summary: a pretty proof that the probability is 1/2^{n-2}.

Schofield, N. and C. Tovey, Probability and Convergence for Supra-Majority Rule with Euclidean Preferences, Mathematical and Computer Modelling , Vol. 16, pp. 41-58, 1992.

Seeley, T. and C. Tovey, Why Search Time is a Reliable Indicator of Nectar Influx in Honey Bee Colonies, Animal Behavior , Vol. 47, pp. 311-316, 1993.

Steinberg, R. and C. Tovey, Planar Ramsey Numbers, Journal of Combinatorial Theory, Series B , Vol. 59, pp. 288-296, 1993. Summary: finds exact values of Ramsey-type numbers when domain is restricted to planar graphs; proves a conjecture of Albertson, Bollobas, and Tucker (1976) that every triangle-free planar graph has an independent set size 1 + \floor{n/3}.

McGinnis, L. F., J. C. Ammons, M. Carlyle, L. Cranmer, G. W. DePuy, K. P. Ellis, C. A. Tovey, and H. Xu, Automated Process Planning for Printed Circuit Card Assembly, IIE Transactions on Scheduling and Logistics , Vol. 24, No. 4, pp. 18-30, September 1992.

Tovey, C. A., A Polynomial Time Algorithm for Computing the Yolk in Fixed Dimension, Mathematical Programming , Vol. 57, pp. 259-277, 1992. Summary: McKelvey's yolk solution concept for the spatial model of voting can be computed in poly time for any fixed dimension.

Ammons, J. C., M. Carlyle, G. DePuy, K. Ellis, L. McGinnis, C. Tovey, and H. Xu, Productivity Improvements in SMD Placement Through CAPP, Proceedings of the International Society of Hybrid Microelectronics Conference , San Francisco, California, October 19-21, 1992.

Rardin, R., C. Tovey, and M. Pilcher, Analysis of a Random Cut Test Instance Generator for the TSP, in P. Pardalos, editor, Complexity in Numerical Optimization , World Scientific Press, 1993. Summary: instances of the traveling salesman problem generated by the Pilcher-Rardin-Reis generator are of intermediate complexity, NP-complete but not D^P-complete.

Tovey, C. A., Some Foundations for Empirical Study in the Spatial Model, in W. Barnett, M. Hinich and N. Schofield, editors, Political Economy: Institutions Information and Competition," Cambridge University Press, 1993.

Ammons, J. C., M. Carlyle, G. W. DePuy, K. P. Ellis, L. G. McGinnis, C. A. Tovey, and H. Xu, Computer Aided Process Planning in Printed Circuit Card Assembly, IEEE-CHMT Transactions , Vol. 16, No. 4, June 1993.

Chandra, B., H. Karloff, and C. Tovey, New Results on the old K-opt Algorithm for the TSP, 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, January 1994. (Full version in 1999.) Summary: 2-opt takes expected polynomial time for random instances in the unit square with L_2 norm, or hypercube with L_1 norm; O(1) expected performance ratio. Worst-case ratio is theta(sqrt{n}) for metric distances, O(log n) and Omega(log n/loglog n) for norm-induced distances. Lueker's result extended, some other results given.

Tovey, C. A., Dynamical Convergence in the Euclidean Spatial Model, Social Choice, Welfare, and Ethics , Cambridge University Press, W. Barnett, H. Moulin, Maurice Salles and N. Schofield, Eds., 1995.

Eben-Chaime, M., C. A. Tovey, and J. C. Ammons, Circuit Partitioning via Set Partitioning and Column Generation, Operations Research, Vol. 44, pp. 65-76, 1996.

Ammons, J. C., K. Ellis, G. DePuy, L. McGinnis, and C. Tovey, Process Optimization for Electronic Assembly Systems-Industrial Case Studies, Proceedings of the 5 th Industrial Engineering Research Conference , Minneapolis, Minnesota, May 18-20, 1996.

Pendurkar, R., A. Chatterjee, and C. Tovey, Optimal Single Probe Traversal Algorithm for Testing of MCM Substrates, International Conference on Computer Design, Austin, TX October 7-9, 1996, pp. 396-401.

Ammons, J. C., M. Carlyle, L. Crammer, G. W. DePuy, K. P. Ellis, L. G. McGinnis, C. A. Tovey, and H. Xu, Component Allocation to Balance Workload in Printed Circuit Card Assembly Systems, IIE Transactions , Vol. 29, pp. 265-275, 1997.

Tovey, C. A., Local Improvement on Discrete Structures, in Aarts and Lenstra, editors, Local Search in Combinatorial Optimization , Wiley, 1997.

Chandra, B., H. Karloff, and C. Tovey, New Results on the old K-opt Algorithm for the TSP, SIAM Computing , Vol. 28, pp. 1998-2029, 1999.

Baxter, L., F. Harche, and C. Tovey, A Simple Forecasting Heuristic to Balance Processes with Unequal Capacities, Operations and Quantitative Management , 1996.

Tovey, C. A., Probabilities of Transitivity with Super Majority Voting, Journal of Economic Theory , 1997.

N. Calkin, P. Erdos and C. Tovey, Improved Bounds on Ramsey Numbers from Cycle Graphs of Prime Order, SIAM Discrete Math ., Vol. 10, #3, 1997.

Klabjan, O., G. L. Nemhauser, and C. Tovey, The Complexity of Cover Inequality Separation, Operations Research Letters , Vol. 23, pp. 35-40, 1998. Summary: Crowder et al. (Oper. Res. 31, 1983) conjectured that separation for cover inequalities on binary IPs is polynomially solvable. We show that the general problem is NP-hard, even if the IP is a knapsack problem, but a special case is linear time solvable.

Glockner, G., G. Nemhauser, and C. Tovey, Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results, Computational Optimization and Applications , Vol. 18, pp. 233-250, 2001.

Pendurhar, R., C. Tovey, and Chaterjee, A Single Probe Traversal Optimization for Testing of MCM Substrate, IEEE Transactions on CADICS, 1999 Vol. 18, pp. 1178-1191. Summary: probabilistic analysis shows an average-case n^{1/4}factor advantage offered by new technology.

C. Tovey and S. Koenig. Greedy Localization, Proceedings of the International Conference on Intelligent Robots and Systems . 427-432. 2001.

Tovey, C.A., Tutorial on Computational Complexity, Interfaces , Vol. 32, No. 3, pp. 30-61, 2002. Available online from Interfaces. An introduction to NP-hardness for practitioners. Works well for 1st year graduate IE and OR students, too. If you want to use this tutorial for educational purposes, send me email and I'll send you the password.

Kwok, K., B. Dreissen, C. Phillips, and C. Tovey, Analyzing the Multiple Target-Multiple-Agent Scenario using Optimal Assignment Algorithms, Journal of Intelligent and Robotic Systems, Volume 35, pp. 111-122, September 2002.

Koenig, S., Y. Smirnov, and C. Tovey, Performance Bounds for Planning in Unknown Terrain, Artificial Intelligence, Vol. 147, pp. 253-279, 2003.

Hunsaker, B., A. Kleywegt, M. Savelsbergh, and C. Tovey, Optimal Algorithms for Online Resource Scheduling, SIAM Journal on Discrete Methods , submitted April 2000, accepted Feb 2003.

Chase, I., C. Tovey, D. Spangler, and M. Manfredonia, Individual Differences versus Social Dynamics in the Formation of Animal Dominance Hierarchies, Proceedings National Academy of Science. , Volume 99, No. 8, pp. 5744-5749, 2002.

Regnier , E., G. Sharp, and C. Tovey, Optimal Asset Replacement Under Continuous and Ongoing Technological Progress, IIE Transactions , submitted December 2001, revised 2002, accepted October 2002.

Tovey,C.A. Non-approximability of Precedence-Constrained Scheduling to Minimize Setups, Discrete Applied Math , Vol. 13, pp. 351-360, 2003.

Chase, I., C. Tovey, P. Murch, Two's Company, Three's a Crowd: Differences in Dominance Relationships in Isolated Versus Socially Embedded Pairs of Fish, Behaviour Vol. 140, pp. 1193--1127. slides from a talk here

R. Borie, R. Parker, C. Tovey, Recursively Constructed Graphs, section 2.4 in Handbook on Graph Theory , edited by J. Gross and J. Yellen, CRC Press, 2004.

R. Borie, R. Parker, C. Tovey, Algorithms on Recursively Constructed Graphs, section 10.4 in Handbook on Graph Theory , edited by J. Gross and J. Yellen, CRC Press, 2004.

Kwok, K., B. Driessen, C. Phillips, and C. Tovey, Analyzing the Multiple-target-multiple-agent Scenario Using the Network Simplex Method, SPIE Proceedings Volume 3209 , Sensor Fusion and Decentralized Control in Autonomous Robotic Systems.

Kleywegt, A., V. Nori, M. Savelsbergh, and C. Tovey, Online Resource Minimization, 10 th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, January 1999.

Tovey, C. and S. Koenig, Gridworlds as Testbeds for Planning with Incomplete Information, in Proceedings of the National Conference on Artificial Intelligence , pp. 819-824, 2000.

Koenig, S., C. Tovey and W. Halliburton, Greedy Mapping of Terrain, in Proceedings of the International Conference on Robotics and Automation , pp. 3594-3599, 2001.

Mugdal, A., S. Koenig, and C.Tovey, Analysis of greedy robot-navigation methods, Mathematics and Artificial Intelligence, 2004 .

Tovey, C., S. Greenberg and S. Koenig, Improved Analysis of D*, ICRA Proceedings of the IEEE International Conference on Robotics and Automation 2003.

S. Nakrani and C. Tovey, On Honey Bees and Dynamic Allocation in an Internet Server Colony, Proceedings of 2 nd International Workshop on The Mathematics and Algorithms of Social Insects , Atlanta, Georgia, USA. December 15-17, 2003.

C. Tovey and S. Koenig, Minimizing Localization Travel Distance, accepted in IEEE Transactions on Robotics, 2004.

Submitted or in Preparation

B. Hunsaker and C. Tovey, Simple Lifted Inequalities and Hard Knapsack Problems Summary: Chvatal's hard random knapsack class almost surely requires exponentially many branch and bound nodes, even if all simple lifted inequalities are present.

E. Regnier and C. Tovey, Time Lags of Environmental Costs.

S. Greenberg, S. Koenig, A. Mugdal, C. Tovey, Bounds on the Travel Cost of the Mars Rover Prototype Heuristic.

Joy Bhadury and Craig Tovey, An Improved Algorithm and Analysis for Finding the Simpson Point of a Convex Polygon in Competitive Location, in review

S. Koenig, A. Mudgal, C. Tovey, An Approximation Algorithm for the Robot Localization Problem Summary: First approximation algorithm for robot localization (the robot has a map and compass; it must determine its location in minimum movement). The algorithm is strongly polynomial with O(log^3 n) peformance guarantee. Tovey and Koenig (above) show c log n approximation is NP-hard.

Other Publications

Tovey, C. A., Integrating Karmarkar's Algorithm in the Curriculum, OR/MS Today , 1988.

Modeling in Industrial Engineering , Pearson Custom Publishing, 1999, 2000. (Textbook for IE 2030). (Edited)