Jan Karel Lenstra

IFORS Distinguished Lecture

INFORMS Atlanta Meeting
3:10 – 4:00 PM
Tuesday, October 21, 2003


IFORS Immediate Past President Andres Weintraub (left), presents the IFORS Award to ITL Jan Karel Lenstra

Minimum Test Sets
Jan Karel Lenstra
General Manager, CWI, the Centre for Mathematics and Computer Science

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.

About the Awardee

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.