Computer Scientists Break Traveling Salesperson Record

Posted on by
1

I read the title, “Computer Scientists Break Traveling Salesperson Record,” and was excited to read more.  Algorithmic analysis and improvement is the most impactful and lasting of performance optimizations.  It is not my field, so the impact of the work often eludes me but I enjoy reading such articles nonetheless.

The TSP is still intractable — no surprise there.  The goal rather is to find an “efficient” algorithm (ie, polynomial time) for an approximate solution.  I should add: for a good approximate solution.  The record part is how good is the approximate solution.

The previous record found solutions that were at within 50% of optimal (worst case, I believe).  The new solution is “0.2 billionth of a trillionth of a trillionth of a percent” better than the previous.  I re-read it a few times to find to make I wasn’t missing something.  But that was it.  This is the big news.  An improvement of 0.2 x 10-9 x 10-12 x 10-12.  Percent!  So that is 2 x 10-1 – 9 – 12 – 12 – 2 = 10-36, which is

0.0000000000000000000000000000000000002

better.

Suppose with the previous algorithm the best solution takes 40 minutes.  With the new algorithm the best solution takes only 40 minutes.   Makes one think, doesn’t it.  Once again the impact of this research has eluded me.

CSC 501 Spring 2021 preview

Posted on by
Reply

I will be teaching CSC 501 asynchronously in the Spring.  This will be the first time I’ve taught 501 asynchronously.  I am still designing the course.  Also, the university has not posted the calendar for the Spring term.  However, students are asking about the course.  Therefore, I will provide what I know now.

Each week students will be expected to view approximately 2-2.5 hours of video, delivered in 2+ distinct videos.  Student will read chapters from the textbook and papers.  Additionally, there will be a weekly homework assignment that covers the reading material.  This might be a short programming assignment, a problem set, or a written assignment.

There will be one final exam.  Instead of midterms, there are 5 quizzes given every 3 weeks.  The final and the quiz will be taken online via the moodle quiz module.

Last, there are 4 programming assignments.

Grading is projected to be (it may change): 60% programing, 15% final, 15% quizzes, 10% homework.

The primary textbook is online which costs $0.  (You’re welcome.)  This will be supplemented with many papers.

I’m offering this as an asynchronous class to accommodate student needs and desires.  However, interaction between student and teacher is vital to learning.  Therefore, I will hold synchronous discussion session each week.

Here is the syllabus from the last time I taught this course, which may provide a few more insights into the course.