Stanford
University
MS&E 217,
Combinatorial Optimization
Autumn
200304
Home  Handouts  General Information
Announcements 



Class Information 



Syllabus, Evaluation, homeworks 

Please
see the general
information page. 

Discussion sessions schedule 


Optional Excercises

1.1 

Consider
the following algorithm:
Answer:
No. The definition in class said that an algorithm is efficient if its
running time is polynomial in the input size. In this case, the input is n.
But to write down the integer n, we need roughly log n bits. So the “size” of
the input is only X = log n. The
running time of the algorithm is sqrt(n), which is polynomial in n, but NOT
in the input size X; it isO( 2^{X/2}) which is exponential in the
input size. 


2.1 

Show
that there exists an infinite series of relaxations for the following graph: Answer:
The pattern of relaxations ab,bc,ca can be repeated infinitely often. 


3.1 

Find
a simple modification to the BellmanFord algorithm (as discussed in class)
that enables it to determine if a negative cost cycle exists. Answer:
Run the algorithm for n iterations as opposed to n1; if any potential
changes in the nth iteration, then there exists a negative cycle. 


5.1 

Show
that for the fractional knapsack problem, it is sufficient to examine
finitely many possible allocations. Answer:
At most one item is picked fractionally, and can be picked in n different ways.
We can pick up any subset of the remaining n1 items, which makes a total of
at most n2^{n1} possible choices. 


6.1 

What
impact do –ve weight edges have in the minimum spanning tree problem? Is
there a simple preprocessing step that gets rid of –ve weight edges? Answer:
Minimum weight edges have no impact on the mst problem. Also, we can add a
large positive value to each edgeweight to make sure all edge weights are
nonnegative. 


16.1 

Prove
that in the case when we are given both lower bounds l_{e }and upper
bounds u_{e} on the flow x_{e} through an edge, we can assume
l_{e} ≠ ∞. Hint:
Read page 98 on the text and exercise 4.1. 


17.1 

Show
that there exists a set of preferences such that the stable mrriage algorithm
of Gale and Shapley requires Omega(n^{2}) days to complete. 


18.1 

Suppose
G is a bipartite graph and M is a matching in G. Use maxflow/mincut
techniques to prove that there is no Maugmenting path iff M is a maximum matching.
