Added an abstract for Bill Cook's talk.
authorTheo Belaire <theo.belaire@gmail.com>
Mon, 20 Oct 2014 16:00:30 +0000 (12:00 -0400)
committerTheo Belaire <theo.belaire@gmail.com>
Mon, 20 Oct 2014 16:01:56 +0000 (12:01 -0400)
events.xml

index 441db53..9f2e0c2 100644 (file)
   <short>
     <p>
         Bill Cook is giving a talk about the Traveling Salesman.
+The problem is easy to state: given a number of cities along with the cost of
+travel between each pair of them, find the cheapest way to visit all of them
+and return to your starting point.  Easy to state but difficult to solve.  In
+this talk we discuss the history, applications, and computation of this
+fascinating problem.
     </p>
   </short>
+  <abstract>
+    <p>
+        The traveling salesman problem is easy to state: given a
+        number of cities along with the cost of travel between each
+        pair of them, find the cheapest way to visit them all and
+        return to your starting point.  Easy to state, but
+        difficult to solve.  Despite decades of research, in
+        general it is not known how to significantly improve upon
+        simple brute-force checking.  It is a real possibility that
+        there may never exist an efficient method that is
+        guaranteed to solve every instance of the problem.  This
+        is a deep mathematical question: Is there an efficient
+        solution method or not?  The topic goes to the core of
+        complexity theory concerning the limits of feasible
+        computation and we may be far from seeing its
+        resolution. This is not to say, however, that the
+        research community has thus far come away
+        empty-handed.  Indeed, the problem has led to a large
+        number of results and conjectures that are both
+        beautiful and deep, and on the practical side solution
+        methods are used to compute optimal or near-optimal tours
+        for a host of applied problems on a daily basis, from
+        genome sequencing to arranging music on iPods.  In this
+        talk we discuss the history, applications, and
+        computation of this fascinating problem.
+    </p>
+  </abstract>
+
 </eventitem>
 
 <eventitem date="2014-09-18" time="6:00 PM" room="MC 4021"