### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Special Topics MAT 180

UCD

GPA 3.88

### View Full Document

## 33

## 0

## Popular in Course

## Popular in Mathematics (M)

This 7 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 33 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?

#### Karma is the currency of StudySoup.

#### 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 20 Matthias Koppe UC Davis Mathematics March 12 2009 The PrimalDual Algorithm reminder PrimalDual Algorithm Input Graph G VA capacities u excess values b costs c 0 Construct a pair of initial solutions x y a Whilex is not feasible If there exists an xaugmenting path P of equality arcs Determine the width of the path Augment the flow x along P Otherwise Find a vertex set R blocking all such paths and change y for all v E VF1 as described on page 18 12 a We were not happy with this algorithm because it seems we may need quite a number of dual steps change of potentials until we can make the next primal step sending flow from an xsource to an xsin The PrimalDual Algorithm complexity analysis a To be more precise Because each dual step increases the size of the blocking set R by at least one vertex at most n7 1 dual steps are necessary a For integervalued data it is clear that each primal step augmenting flow decreases the imbalance by at least 1 so the number of augmentations is bounded by the initial imbalance on Zmax0 by 7 fxov V where x0 is the initial feasible solution a For nonnegative costs we could start with the zero flow x0 0 so we have at most Bo Zmax0 by V augmentations So again we will get a pseudopolynomial algorithm of running time OSn m n on where 8n m is the running time of a shortestpath computation 0 Knowing this more precisely does not make us happier though PrimalDual Algorithm with LeastCost This observation suggests a new algorithm due to Busacker Gowen 1961 PrimalDual Algorithm with LeastCost Augmenting Paths Input Graph G VA capacities u excess values b costs c 0 Construct a pair of initial solutions x y o Whilex is not feasible Find a leastcost with respect to reduced costs 6 xincrementing path P from an xsource to v for each v E V one nonnegativecost shortestpathtree calculation in a graph with an artificial source denote by 5 the costs of the paths Choose an xsink s such that as is minimum Update the potentials y z y minoos for v e V Augment x on PS This algorithm maintains the optimality conditions on x and y in each step 2 Efficiency of Algorithm Initial Feasible Solution 0 Because the dual update can be done in one step using a single shortestpathtree computation this is quite a bit faster The running time reduces to OSnm non o How do we construct a pair of initial solutions by the way a If all costs are nonnegative can use x 0 y 0 0 We could try to sety O or arbitrary and set XVYW UVW if EVYW lt 0 and XVYW 0 to satisfythe optimality conditions However this fails if some UVW oo a General solution updated a Solve a maximumflow problem to find out whether there is a feasible flow discard the solution 0 Solve a shortest path problem in a directed graph G that only has the arcs with infinite capacities using the original costs c o If there is no feasible shortestpath potential there exists a negativecost directed cycle of infinite capacity so the problem is unbounded no optimal solution 9 Otherwise we obtain a feasible shortestpaths potential y on 6 so we ave yw g yV 0VW for all v w with UVW oo a We use this y as the initial potential From the above inequality we have EVYW 2 0 for all arcs v w with UVW oo 0 Now set XVYW UVW if EVYW lt 0 and XVYW 0 Note that no XVYW will be infinite 2040 o By a scaling technique where demands by are replaced by by2H Edmonds Karp 1972 obtained a polynomialtime variant The running time is 0n 8n m 1 log maxBo U where U is the largest finite arc capacity 0 The scaleandshrink algorithm following from work by Tardos 1985 Orlin 1985 Fujishige 1986 is a strongly polynomialtime variant with a running time of 0mo nnlog n 8n m 2041 Th e s much more of optimization to learn We have only scratched the surface a MAT168 Spring 2009 Linear Programming 0 20092010 Yearlong program VIGRE RFG on optimization 9 Optimization seminar 0 Reading courses 9 258A Fall 2009 Numerical Optimization 0 2588 Winter 2010 Variational Analysis and MixedInteger Nonlinear Programming 9 280 Spring 2010 Integer Programming 2042

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "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."

### 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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.