Jump to Content: Welcome to the virtual world of Georgia Tech

Jump to Footer Navigation: Accessibility | Contact Us | Legal & Privacy Information | Technology

School of Industrial and Systems Engineering at Georgia Tech

Assistance Navigation:

Campus Map Directories Site Map Site Help Site Search
Faculty Webpage

Craig Tovey Website

crumb trail: GT >> College of Engineering >> School of Industrial and Systems Engineering >> ISyE Personal Web Site

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. In Dantzig's column geometry, the simplex method and the projective scaling interior point methods are closely related.

Lofgren, C., L. McGinnis, and C. Tovey, Routing Printed Circuit Cards Through an Assembly Cell, Operations Research , Vol. 39, pp. 992-1004, 1991. Complexity and heuristic results for precedence-constrained routing through a flexible manufacturing system.

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. NP-hardness of the existence of equilibrium in the spatial Euclidean model. NP-hardness of the Nakamura number. Unless NP=co(NP) there are no succinct necessary and sufficient conditions for the existence of equilibrium.

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 ).

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.

Tovey, C.A., Asymmetric Prospects of Stackelberg Players, Journal of Optimization Theory and Applications (JOTA), Vol. 68, pp. 139-159, 1991.

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

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.

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

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.

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.

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.

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.

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}.

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. Establishes basic convergence and algorithms for solution concepts in the spatial model.

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.

Llewellyn, D. C. and C.A. Tovey, Dividing and Conquering the Square, Discrete Applied Mathematics , Vol. 42, 1993. Finding a local optimum in a square.

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. A sequence of winning proposals will converge to an epsilon-equilibrium, at rate controlled by the yolk radius.

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.

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.

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.

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. 1997, pages 111-122.

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.

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.

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.

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.

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.

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

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.

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..

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.

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. First experimental verification of a self-organizing social structure!

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 , Vol 16, pp. 555-590, 2003.

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, 2003, pp. 1193--1127. slides from a talk here . Reveals a fundamental problem in the analysis of dominance hierarchies. Tradiitonally, we study one pairwise relationship at a time, but isolated pairs don't behave the same as pairs in situ i.e. in a group. To access this secure document, use ID secure and use password toveysecure.

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.

S. Nakrani and C. Tovey, “Autonomic Server Allocation,” 8th International Conference on Parallel Problem Solving from Nature,Workshop on Nature Inspired Approaches to Networks and Telecommunication,18—22 September, Birmingham, U.K., Springer-Verlacht, Lecture Notes in Computer Science, No. 3242, 2004.

Regnier , E., G. Sharp, and C. Tovey, Replacement Under Ongoing Technological Progress, IIE Transactions, Volume 36, No. 6, pages 497-508, June 2004.

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.

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

Ery Arias-Castro, David Donoho, Xiaoming Huo, and Craig Tovey, “Connect-The- Dots: How many random points can a smooth curve pass through?”, Advances in Applied Probability, 2005, volume 37, pp. 571—603.

C. Tovey, M. Lagoudakis, S. Jain and S. Koenig; The Generation of Bidding Rules for Auction-Based Robot Coordination; Lecture Notes in Artificial Intelligence; Proceedings
of the Third International Multi-Robot Systems Workshop; A. Schultz, L. Parker and F. Schneider (Eds.); Springer; pages 3-14, 2005.

M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson and S. Jain, Auction-Based
Multi-Robot Routing
, Proceedings of the International Conference on Robotics: Science and Systems (RoSS), 2005, pages 343-350, Cambridge, USA (plenary presentation).

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. Discrete Optimization, Vol. 2 No. 3: pages 219-228 (2005).

S. Greenberg, S. Koenig, A. Mugdal, C. Tovey, Bounds on the Travel Cost of the Mars Rover Prototype Heuristic. SIAM Journal on Discrete Mathematics, 2005, Volume 19 Issue 2, pages 431–447.

Zheng, Koenig, and Tovey, "Improving Sequential Single-Item Auctions", Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS06), pages 2238-2244, Beijing, October 2006. Appeared also in: Proceedings of the AAI-06 Workshop on Auction-Mechanisms for Robot Coordination, 2006.

Sven Koenig, Apurva Mudgal, and Craig Tovey, “Near-Tight Approximation Algorithm and Bounds for the Kidnapped Robot Problem”, Proceedings of the Seventeenth ACM SIAM Conference on Discrete Algorithms (SODA06), Proceedings in Applied Mathematics 122, 2006.

T-X Wu, D. Goldsman, J. Sokol, C. Tovey, "General Adoption Model and Cultivation Effect", Proceedings of 36th International Conference on Computers and Industrial Engineering, (ICCIE) 2006; Taipei, Taiwan.

Sven Koenig, Craig Tovey, Michail Lagoudakis, Vangellis Markakis, , David Kempe, Pinar Keskinocak, Anton Kleywegt, Adam Meyerson, Sonal Jain. The Power of Sequential Single-Item Auctions for Agent Coordination. Proceedings of the Twenty-First National Conference on Artificial Intelligence, July 2006, AAAI Press, Menlo Park, pages 1625-1629 [Nectar Paper].

Sven Koenig , Craig A. Tovey, Xiaoming Zheng , Ilgaz Sungur : Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2007, pages 1359-1365 (Plenary Presentation).

Sunil Nakrani and Craig Tovey, From honeybees to Internet servers: biomimicry for distributed management of Internet hosting centers," 2007, Bioinspiration and Biomimetics 2 S182-197, doi:10.1088/1748-3182/2/4/S07. Prepublication version here.

E. Regnier and C. Tovey,Time horizons of environmental versus non-environmental costs: evidence from US tort lawsuits, ”, Business Strategy and
the Environment
, 16 (4), pages 249-265 (2007). Prepublication version here.. In this study, we find that environmental costs take twice as long (10 years versus 5 years) to manifest as do other costs. Because events in the future are highly discounted, this helps explain why decisions leading to environmental degradation are often made. If the discount rate is being used as a proxy for uncertainty, the longer time lag leads to overly risky decisions.

R. Borie, R. G. Parker, C. Tovey, "Solving Problems on Recursively Constructed Graphs", ACM Computing Surveys,Vol. 41, December 2008.

S. Koenig, X. Zheng, C. Tovey, R. Borie, P. Kilby, V. Markakis, P. Keskinocak, “Agent Coordination with Regret Clearing”, Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 101-107, 2008.

Braden Hunsaker, Ellis Johnson, Craig Tovey, “Polarity and the Complexity of the Shooting Experiment,” Discrete Optimization, Special Issue in Memory of George Dantzig, 2008, Vol. 5, #2, pages 541-549.

B.Shepardson, D. Shepardson, F. Shepardson, S. Chui, M. Graves, C. Tovey, “Re-Examining the Evidence for Late Colonization on Easter Island”, Rapa Nui Journal, Volume 22, #2, October 2008, erratum April 2009.

Dylan Shepardson and Craig Tovey, Smallest Tournaments not Realizable by 2/3-Majority Voting, Social Choice and Welfare 2009, Vol. 33, pp. 495-503. Prepublication version here. 8 vertices are needed, answering a question of Gilboa's. The graph is realizable with 13/20-voting. There exists a graph on 9 vertices that requires 64/99-voting.

Joy Bhadury and Craig Tovey, An Improved Implementation and Analysis of the Diaz and O'Rourke Algorithm for Finding the Simpson Point of a Convex Polygon, International Journal of Computer Mathematics, volume 87, pages 244-259, 2010.

S. Koenig, J. Mitchell, A. Mudgal, C. Tovey, A Near-Tight 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. Published version: SIAM Journal on Computing 39, (2), 461-490, 2009

Richard McKelvey and Craig Tovey, Approximating the Yolk by the LP Yolk, Mathematical Social Sciences 59(1), pp. 102-109, 2010.. Prepublication version here.

Craig Tovey, The Almost Surely Shrinking Yolk, Mathematical Social Sciences 59(1), pp. 74-87, 2010. Prepublication version here. Gives necessary and sufficient conditions for the yolk radius to converge to zero when voter points are sampled from discrete or continuous distributions.

Craig Tovey, A Critique of Distributional Analysis, Mathematical Social Sciences 59(1), pp. 88-101,2010. Prepublication version here.Reveals and resolves long-standing errors in the use of distributional analysis in the spatial model of voting.

Craig Tovey, The Instability of Instability of Centered Distributions, Mathematical Social Sciences 59(1), pp. 53-73, 2010. Prepublication version here. Puts predictions of spatial model in accordance with observation. Includes a rigorous proof of Tullock's "Why So Much Stability?" argument.

R. Borie, C. Tovey and S. Koenig. Algorithms and Complexity Results for Pursuit-Evasion Problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 59-66, 2009.

A. Nash, S. Koenig and C. Tovey. Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2010.

S. Koenig, P. Keskinocak and C. Tovey. Progress on Agent Coordination with Cooperative Auctions [Senior Member Paper]. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2010.

C. Tovey and S. Koenig, Localization: Approximation and Performance Bounds to Minimize Travel Distance, IEEE Transactions on Robotics, 26 pp. 320-330, 2010.

Craig Tovey, The Probability of Instability in Two Dimensions with an Even Number of Voters, Social Choice and Welfare 2010 volume 35 pages 75-78.. Pre-publication version here.

Craig Tovey, A finite algorithm for epsilon-core membership in two dimensions, Mathematical Social Science 2010 volume 60, pages 178-180.. Pre-publication version here.

Craig Tovey, The Epsilon-Core and the Finagle Point: a comment on Brauninger's proof, J. Theoretical Politics volume 23, pages 135-139. pre-publication version here.

David Hu, Nathan Mlot, Craig Tovey. Fire Ants Assemble Themselves into Hydrophobic Rafts to Survive Floods. Proceedings of the National Academy of Science.

Richard Borie, Craig Tovey, Sven Koenig. Algorithms and complexity results for graph-based pursuit evasion, Autonomous Robots, Vol 41, No. 4, pp. 317-332, 2011

Ashok Goel, Bert Bras, Michael Helms, Spencer Rugaber, Craig Tovey, Swaroop Vattam, Marc Weissburg, Bryan Wiltgen, & Jeannette Yen. Computer-Aided Biologically Inspired Design: A Bridge Between Artificial Intelligence and Sustainable Development. Proc. AAAI Spring Symposia on AI and Sustainable Design, Stanford University, Palo Alto, March 2011

Ashok Goel, Bert Bras, Michael Helms, Spencer Rugaber, Craig Tovey, Swaroop Vattam, Marc Weissburg, Bryan Wiltgen, & Jeannette Yen. Design Patterns and Cross-Domain Analogies in Biologically Inspired Sustainable Design. In Proc. AAAI Spring Symposium on AI and Sustainable Design, Stanford University, Palo Alto, March 2011, pp. 45-51.

Nathan Mlot, Craig Tovey, and David Hu. Dynamics and Circularity of Large Ant Rafts, Communicative and Integrative Biology, Vol 5, pp. 590-597, 2012

Jeannette Yen, Michael Helms, Craig Tovey, Marc Weissburg, and Ashok Goel, Adaptive Evolution of Teaching Practices in Biologically Inspired Design, Biologically Inspired Design: Computational Methods and Tools, Ashok Goel, Daniel McAdams & Robert Stone, editors, pp. 153-199, London, 2014

Eric Tollefson, David Goldsman, Anton Kleywegt, and Craig Tovey, A Comparative Study of Multinomial Selection Problem Procedures, Uzsoy, R. and Sarin, S. and Pulat, S., (eds.) Essays in Planning, Scheduling and Optimization: A Festschrift in Honor of Salah E. Elmaghraby. Springer, New York, 2014

Sam Saarinen, Craig Tovey, and Judy Goldsmith. A Model for Intransitive Preferences. In Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence. 2014

Eric Tollefson, David Goldsman, Anton Kleywegt, and Craig Tovey, Optimal Selection of the Most Probable Multinomial Alternative, Sequential Analysis, vol 33 #4, pp. 491-508, 2014

Craig Tovey, The Slippage Configuration is Always the Least Favorable Configuration for Two Alternatives, Sequential Analysis, vol 33 #4, pp. 509-518,2014

Sam Saarinen, Judith Goldsmth, Craig Tovey, Probabilistic Copeland Tournaments, Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2015), extended abstract, 2015

Sven Koenig, Zachary Suffern, Craig Tovey, Towards Completely Decentralized StarCraft Play with Price of Anarchy Performance Guarantees, Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2015), 2015

Stefano Benati; Romeo Rizzi; Craig Tovey, The Complexity of Power Indexes with Graph Restricted Coalitions, Mathematical Social Sciences, 2015

Martin, Mathieu, Zéphirin Nganmeni, and Craig A. Tovey. "On the uniqueness of the yolk." Social Choice and Welfare 47.3 (2016): 511-518.

Inbal Givli, Marc Weissburg, Jeannette Yen, Michael Helms, & Craig Tovey (2016). Development of Scoring Rubric for Evaluating Integrated Understanding in an Undergraduate Biologically-Inspired Design Course. synthesis, 11, 14.

Hang Ma, Craig A. Tovey, Guni Sharon, TK Satish Kumar, and Sven Koenig. Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem. In AAAI, pp. 3166-3173. 2016.

Invited Book Reviews

Review of Biomimicry for Optimization, Control, and Automationby Kevin Passino, IEEE Control Systems Magazine, August 2006, Vol. 26, Issue 4, pages 86-90

In Defence of Basic Research, Review of "The Usefulness of Useless Knowledge" by Abraham Flexner, Science, February 24 Vol. 355 No. 6327 p. 804

Submitted or in Preparation


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)

epscore5 c code to determine membership in the epsilon core


This site is available to any internet device, but really looks best in a modern graphical browser that supports web standards.

GT website ISyE website GT CoE website