Wednesday, September 10, 2014 10:30 am
-
10:30 am
EDT (GMT -04:00)
David
S.
Johnson
Columbia
University
Wednesday,
Sept.
10th,
10:30
am
DC
1302
TSP
instances
generated
by
placing
cities
uniformly
at
random
within
the
unit
square
provide
reasonable
surrogates
for
the
instances
arising
in
many
real-world
TSP
applications. They
are
also
an
interesting
object
of
study
on
their
own.
The
optimal
tour
length
is
known
to
grow
as
c\sqrt{n}
for
some
constant
c,
but
the
exact
value
of
c
and
the
details
of
the
convergence
rate
have
not
been
determined.
In
this
talk
I
report
on
an
ongoing
study
of
this
and
related
questions
with
David
Applegate
and
Bill
Cook,
based
on
experiments
with
millions
of
instances
using
the
Concorde
software
package.
Interesting
statistical
questions
arise.
--
David
Johnson
was
the
head
of
the
Algorithms
and
Optimization Department of
AT&T
Labs
Research
from
1988
to
2013.
He
was
awarded
the
2010
Knuth
Prize.
Johnson
graduated
summa
cum
laude
from
Amherst
College
in
1967, then
earned
his
S.M.
from
MIT
in
1968
and
his
Ph.D.
from
MIT
in
1973.
All
three
of
his
degrees
are
in
mathematics.
In
1995
he
was
inducted
as
a
Fellow
of
the
Association
for
Computing
Machinery.
Johnson
has
Erdős
number
2.