[go: up one dir, main page]
Scribd
Upload
90 views5 pages

Re-Exam "Discrete: Optimization"

The document summarizes an exam for a "Discrete Optimization" course consisting of 6 problems: 1) Proving properties of spanning trees with edge costs of 0 or 1. 2) Designing approximation algorithms for the maximum traveling salesman problem. 3) Proving NP-completeness of the exact-costs spanning tree problem. 4) Properties of minimum-cost flows and reducing cycle flows. 5) Designing an algorithm for the node surveillance problem using matchings. 6) Stating whether true/false statements about cuts, reductions, and spanning trees are true.

Uploaded by

LotteWeedage
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
90 views5 pages

Re-Exam "Discrete: Optimization"

The document summarizes an exam for a "Discrete Optimization" course consisting of 6 problems: 1) Proving properties of spanning trees with edge costs of 0 or 1. 2) Designing approximation algorithms for the maximum traveling salesman problem. 3) Proving NP-completeness of the exact-costs spanning tree problem. 4) Properties of minimum-cost flows and reducing cycle flows. 5) Designing an algorithm for the node surveillance problem using matchings. 6) Stating whether true/false statements about cuts, reductions, and spanning trees are true.

Uploaded by

LotteWeedage
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Re-Exam "Discrete Optimization"

FYiday, February 20,2OL5, 13:15

16:15

o Use of calculators, mobile phones, and other electronic devices is not


o The exam consists of six problems.

allowed!

Please start a new page for every'problem.

o The total number of points of the regular assignments is 45. You get 5 bonus
points, and you can get 5 bonus points from Exercise lb.

1. Spanning Trees
We consider the problem ExactST0l:

Instance: undirected, connected graph G : (V,.8); edge costs c :


each edge has costs of either 0 or 1; a number k e N.

E -+ {0,1},

i.e.,

Goal: frnd a spanning tree 7 of G such that c(7) :Deerc(e): k (this means that
7 contains k edges of cost 1 and n-k- 1 edges of cost 0), or conclude that no
such tree exists.
As usual, we have

(")

,: lVl and m:

lEl.

(6 points)Prove the following statement: For every undirected, connected graph


G : (V,E) with edge costs c: E -+ {0, 1}, there exist two numbers a, b N with
a 1 b and the following property:

o For every k e {a,a*L,...,b - 1,b}, the graph G contains a spanning tree


7 with c(T) :1x.
o Thegraph Gdoesnot contain aspanningtreeof weight kfor k < aor k> b.

(b)

(5 points) Devise a polynomial-time algorithm for ExactST0l. Prove that your


algorithm is correct and analyze its running-time.

(")

(5 bonus points) Devise an algorithm for ExactST0l that has a running-time of


O(mlogrn). Prove that your algorith'm is correct and satisfies the running-time
bound.

If you solve this'part correctly, you

also get the points of

Part (b).

2. Traveling Salesman Problem


Our goal is to find an approximation algorithm for MaxTSP:
Instance: undirected, complete graph G

Solution: aHamiltoniancycle
Goal: rnaximize

(V.,8) with edge weights tu : E -+

iR.+.

He Eof G.

*(H) : D"rn w(e).

For an instance G : (V,E) and w for MaxTSP, let H* be a Hamiltonian cycle of


G of maximum weight.
In the following, we assume that the number n of nodes is even.

(")

(3 points) Let M* be a maximum-weight perfect matching of the graph G with


edge weights tr.r.
Prove that w(M*)

(b)

> +..(H.).

(4 poi,nts) Devise a polynomial-time approximation algorithm for MaxTSF. Your


algorithm should output a Hamiltonian cycle fI with w(H) > * ..(H.).

3. NP-Completeness
The exact-costs spanning tree problem, denoted by ExactST, is the following
decision problem:

Instance: undirected graph

G:

(V,E),

Question: is there a spanning tree

edge costs c :

E -+ N, number k e N.

7 of G such that c(?) : D.er c(e) :

1xt

(7 poi.nts)Prove that ExactST is NP-complete.

Hi,nt: You can reduce from SubsetSum, which is the following problem and known
to be NP-complete:
Instance: n items with weights tui,
Questi,on: is there a subset

... ,wn e N, number k e N.

/ q {1, ...,n} of the items such that w(I) :lnrrwi:

k?

Remark: Note the difference to Exercise 1 - in Exercise 1, only costs 0 and 1 are
allowed; here, arbitrary natural numbers are allowed as costs.

4. Minimum-Cost Flows
Let G : (V,E) be a flow network with budgets b : V -) Z, capacities u : E -+ N, and
costs c : E -+N. For a feasible flow / : E -+lR+ on this network, let H : (V,Df)
be an undirected graph with the same set V of nodes as G and with the following set
Dy of edges:
D : {{", r} I @,u) > 0 and (u,,u) < w(u,u)}.

This means that the edge set D7 contains an undirected edge {u,r} if the edge
(u, u) e .B is neither saturated nor empty under the flow /.
For simplicity, you can assume that G does not contain pairs of reversed edges, i.e.,
t (u,,u) E, then (u,u) ( E.
Erample: The left-hand side shows a flow network including a flow /, the right-hand
side shows the corresponding graph Dy. Budgets are written inside the nodes. The
edge labels are "flowf capacity". Costs are omitted as they do not play a role in this
example.

ffi
x"

(")

\)/

-1

the following: Let / be a feasible flow. If the graph .FIy contains


a cycle, then / can be written as the convex combination of at least two other
feasible flows 91 and, 92 such that lDnrl,lDn,| < lDrl. This means that the graphs
Hn, and Ir, contain fewer edges than -Iy.
(S poi,nts)Prove

(b) (3 points)Prove the following:


such

that D1. is a forest.

There exists a feasible flow

/* of minimum cost

5. Matchings
The node surveillant problem (denoted by NodeSurv) is the following decision
problem: An instance of NodeSurv is an undirected graph G : (V,E) with budgets
, e N for all nodes u e V. A node u N can surveil at most , of the edges adjacent
to it.
Our goal is to assign the edges to the nodes such that as many edges as possible
are surveilled.
(6 points)Devise a polynomial-time algorithm for determining the maximum number of edges that can be surveilled.

Remark: You can use a (polynomial-time) subroutine for computing bipartite matchings of maximum cardinality as a black box. A proof of correctness of your algorithm
is not needed, but you should give a brief explanation why it works. A formal analysis
of the running-time is also not needed, if it is clear that it is polynomial.

Erample: In the four examples below, the budgets are written inside the nodes. In
the two graphs on the left-hand side, all edges can be surveilled. This means that the
ans\Mers are "5" and "8". In the third graph, the answer is "4". In the fourth graph,
the answer is "7" .

6. Tlue or False
Are the following statements true or false? Justify your answer.

(")

(Z points) Assume that you have a flow network with source s and sink , an s-
(x,N), and a flow Then the capacity of the cut (x, X) is at least the flow

cut

value of

(b)

(2

i.e.,
"f ,

points)If

/.

c(X,X) > l/l

Knapsack can be solved in polynomial time, then 3SAT can be solved

in polynomial time.

(") (2 points) Let G : (V,E)

be a connected graph consisting of at least three


vertices, andletTbeaspanningtreeof G. Then,forall X gV with0 *X *V,
there is exactly one edge in ? crossing the cut (X, X).

(d) (2 poi,nts)There is a pol)momial-time

many-one reduction from PerfectMatch


undirected
graph
perfect
G
contains
a
matching} to 3SAT.
{G I

You might also like