×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## Special Topics

by: Otilia Murray I

20

0

3

# Special Topics MAT 180

Otilia Murray I
UCD
GPA 3.88

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
3
WORDS
KARMA
25 ?

## Popular in Mathematics (M)

This 3 page Class Notes was uploaded by Otilia Murray I on Tuesday September 8, 2015. The Class Notes belongs to MAT 180 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/187391/mat-180-university-of-california-davis in Mathematics (M) at University of California - Davis.

×

## Reviews for Special Topics

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/08/15
Mathematics for Decision Making An Introduction Lecture 3 Matthias KOppe UC Davis Mathematics January 14 2009 The Traveling Salesperson Problem Traveling Salesperson Problem TSP A traveling salesperson needs to visit n cities starting from city 1visiting each other city exactly once and returning to city 1 Find the shortest possible such tour Distances between the cities can be measured in different ways 0 If cities are considered as points y 6 R2 a useful distance between cities could be the Euclidean distance dUJ xXI XIF TO I in o Other distances that make sense are Number of miles on the shortest road connection between cities iand j airfares in US dollars Some of these distance functions 0 have some of these properties a Satisfies triangle inequality Metric TSP 03 S d3k WV 0 Symmetry Symmetric vs Asymmetric TSP 6103 KM Some comments on the TSP The TSP is one of the most famous combinatorial optimization problems 0 It appears in a wide array of applications 0 Various route planning problems 9 Printed circuit board drilling 0 Application in genome sequencing a It is notoriously hard to solve o A symmetric TSP has n712 possible tours so brute force is not feasible 0 Simple intuitive heuristics such as the visitnearestneighbor algorithm fail spedacwany No efficient algorithm is known for it today and it belongs to a huge class NPhard of other seemingly unrelated difficult problems that we could suddenly solve efficiently once an efficient algorithm for TSP became available 0 We ll find out how well our blackbox optimization solver works for this model Excellent web resource by Prof William Cook Georgia Tech http wwwtspgatech edu o Concorde stateofthe art software for TSP world records on the TSP applications and illustrations

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com