Title of Presentation: Minimum Test Sets

INFORMS Atlanta Meeting

3:10 – 4:00 PM

Tuesday, October 21, 2003

Abstract:

Given a number of items and a collection of subsets, called tests, find a smallest number of tests that enable one to distinguish between each pair of items. I will describe several practical settings in which this problem occurs and discuss a variety of approaches to obtain optimal or approximate solutions. I will make an attempt to put these approaches in a historical context.

Bio

Jan Karel Lenstra is General Manager of CWI, the Centre for Mathematics and Computer Science in Amsterdam. He has been on the research staff of CWI; on the faculty of the Technische Universiteit Eindhoven, where he served as Dean of Mathematics and Computer Science; and at the Georgia Institute of Technology. His research interests are in combinatorial optimization-in particular sequencing and scheduling, complexity, approximation and local search. He is co-editor of 15 books, including The Traveling Salesman Problem, History of Mathematical Programming and Local Search in Combinatorial Optimization. He has been chair of the Mathematical Programming Society and of the Koninklijk Wiskundig Genootschap, and editor-in-chief of Mathematics of Operations Research. He is editor-in-chief of Operations Research Letters.