Algorithms in the "Real World":
A Round Table on Applications of Algorithms in Industry


McConomy Auditorium
University Center
Carnegie Mellon University
Pittsburgh, PA

May 25-26, 2000

[Speakers | Summary | Talk Schedule | Registration | Organizers ]


Marshall Bern Xerox PARC
Randy Bryant Carnegie Mellon University
Andrew Goldberg Intertrust
Monika Henzinger Google
David Johnson AT&T
Richard Karp MSRI, ICSI and UC Berkeley
Kurt Mehlhorn Max Planck Institute, Saarbrucken
Silvio Micali Massachusetts Institute of Technology
Eugene Myers Celera Genomics
Alejandro Schaffer National Institutes of Health
Robert Tarjan Princeton University
Michael Trick Carnegie Mellon University


Interesting algorithms arise in many industrial applications in a broad variety of areas. Getting a better understanding of where and how these algorithms are used can be valuable in many ways. It can help in the teaching of algorithms by supplying up-to-date examples of the contexts in which algorithms are used. It can help make effective use of algorithms in industry by allowing better sharing of experiences. It can help motivate new problems to consider, or can improve our understanding of the models and the assumptions we make in various problem domains. It can give us a better feeling of what it takes to have industry use algorithms, and it can help us better understand what factors are important in the design of algorithms.

The speakers will consist of mix of researchers in academia who have interacted with people in industry or worked on industrial applications, and industry people who are using algorithms in their work. The speakers will cover a variety of "application areas", although the topics are certainly not meant to be comprehensive.

Some Topics of Discussion will include:

  • What should we teach in algorithms courses?
  • What is the process of getting algorithms used in industry?
  • How important are constants and how important are asymptotics in practice?
  • How long should we expect it to take for new theoretical algorithms to appear in applications. 10 years? 20 years?
  • Should we put together a repository of examples of algorithms and their applications?
  • Are there application domains in which algorithms should be playing a larger part?
  • How do we deal with the tension between (a) creating broadly useful algorithms for generic problems, and (b) meeting the needs of a specific client.
  • The real world is noisy. How should algorithms deal with noisy input data?
  • The workshop is partially motivated by a course on Algorithms in the "Real World".

    Talk Schedule

      Breakfast Buffet
      Session 1: 
        9:15-9:45: Introduction
        9:45-10:20: Monika Henzinger
       10:20-10:55 Andrew Goldberg
      Session 2:
       11:25-12:00 Silvio Micali
       12:00-12:35 Robert Tarjan
      Session 3:
       2:00-2:35 Richard Karp
       2:35-3:10 Alejandro Schaffer
       3:10-3:45 Eugene Myers
      Breakfast Buffet
      Session 1: 
        9:00-9:35: Randy Bryant
        9:35-10:10: David Johnson
        10:10-10:45: Michael Trick
      Session 2:
       11:20-11:55 Marshal Bern
       11:55-12:30 Kurt Mehlhorn
      Kanellakis Talk:
       2:00-3:00 Sleator/Tarjan


    Guy Blelloch, Daniel Sleator, and Manuel Blum.

    Advisory Committee

    David Johnson AT&T
    Richard Karp UC Berkeley
    Udi Manber Yahoo
    Michael Trick Carnegie Mellon University

    Registration and Hotel Information

    The registration fee is free in advance or $50 at the workshop. For the free advanced registration please send a note to Keith Ledonne ( with your name, affiliation and address by May 5. There will be a desk set up in front of the "Connan Room" at the University Center (map) for onsite registration and any other information.

    There is a block of rooms reserved for the workshop at the Holiday Inn Select in Oakland. This is about a 20 minute walk (directions) from the University Center. Other nearby hotels include:

    Hampton Inn
    3315 Hamlet Street
    Pittsburgh, PA 15213
    Tel: (412) 681-1000

    Pittsburgh Athletic Association
    4215 Fifth Avenue
    Pittsburgh, PA 15213
    Tel: (412) 621-2400

    Taxi service from the Pittsburgh International Airport to the campus/hotels is approximately $30-35. Town car/limousine services are between $40-45.

    Airport Transportation Oakland shuttle service to the Holiday Inn and Hampton Inn Hotels is $12.50 (one-direction) and $21.00 roundtrip. The Pittsburgh Athletic Association is next door to the Holiday Inn. Guests staying at this facility should take this shuttle and walk across the street to their hotel.

    If you are driving we have a number of parking passes for the East Campus garage (marked in red as "parking garage" in this map) these will be available on a first-come-first serve basis. You can park in the garage and then pick up your permit and bring it back to your car.

    Directions to Carnegie Mellon.

    Campus Map. The Holiday Inn is just off this map on the right side as you continue on Fifth Ave.

    Pittsburgh Map

    Related workshops/conferences

  • Workshop on Algorithm Engineering and Experimentation
  • Workshop on the Theory and Practice of Integer Programming in honor of Ralph E. Gomory on the Occasion of his 70th Birthday
  • DIMACS Workshop on Graph Theoretic Methods in Computer Vision

  • Sponsors:

    This workshop is sponsored by the National Science Foundation and Carnegie Mellon University.

    For more information contact:

    Keith Ledonne
    (412) 268-7660