(1) Prove , that the set cover problem is in class NP a)Optimization formulation

Question

(1) Prove, that the set cover problem is in class NP   
a)Optimization formulation
b)Decision formulation
c)Polynomial-size certificate
d)Polynomial time verification algorithm

==========

(2) In the following graph find
maximum independent set_____________
maximum clique_____________________
minimum vertex cover_________________

Below given a point set in the Euclidean metric consisting
of points (0,1), (1,0),(1,1), (1,2), (2,1). Draw

- Voronoi regions (dashed edges)
-  Voronoi graph / Delanau triangulation (solid edges)
- minimum spanning tree (double edges)   

Explanation / Answer

Proof :

First, we argue that Set Cover is in NP, since given a collection of sets C, a certifier can

efficiently check that C indeed contains at most k elements, and that the union of all sets listed in C

does include all elements from the ground set U.

We will now show that Vertex Cover _P Set Cover. Given an instance of Vertex Cover (i.e. a graph

G = (V,E) and an integer j), we will construct an instance of the Set Cover problem. Let U = E.

We will define n subsets of U as follows: label the vertices of G from 1 to n, and let Si be the set of

edges that incident to vertex i (the edges for which vertex i is an end-point). Note that Si _ U for all

i. Finally let k = j. This construction can be done in time that is polynomial in the size of the Vertex

Cover instance. We now run our black box for the Set Cover problem and return the same result it

gives.

To prove that this answer is correct, we simply need to show that the original instance of Vertex

Cover is a yes instance if and only if the Set Cover instance we created is also a yes instance.

Suppose G has a vertex cover of size at most j. Let S be such a set of nodes. By our construction, S

corresponds to a collection C of subsets of U. Since we defined k = j, C clearly has at most k subsets.

Furthermore, we claim that the sets listed in C cover U. To see this, consider any element of U. Such

an element is an edge e in G, and since S is a vertex cover for G, at least one of es endpoints is in

S. Therefore C contains at least one of the sets associated with the endpoints of e, and by definition,

these both contain e.

Now suppose there is a set cover C of size k in our constructed instance. Since each set in C is

naturally associated with a vertex in G, let S be the set of these vertices. |S| = |C| and thus S contains

at most j nodes. Furthermore, consider any edge e. Since e is in the ground set U and C is a set cover,

C must contain at least one set that includes e. But by our construction, the only sets that include e

correspond to nodes that are endpoints of e. Thus, S must contain at least one of the endpoints of e.

We have now shown that our algorithm solves the Vertex Cover problem using a black box for the

Set Cover problem. Since our contruction takes polynomial time, and we have shown that Set Cover

is in NP, we can conclude that Set Cover is NP-Complete.

This particular proof was fairly easy, because, as the proof indicates, Vertex Cover is basically

a special case of Set Cover. Note that showing that a general instance of Set Cover can be solved

using a black box for Vertex Cover would be much more difficult (although clearly possible, since both

problems are NP-Complete).

2

Formulating an Optimization Problem

Outline

1 The Importance of a Good Formulation

2 The Standard Formulation

3 Graphic Solution and Optimization Outcomes

The Importance of a Good Formulation

Model-based Optimization

Procedure:

Problem

to solve

Modeling Mathematical

program

Decisions Solutions

Inference

Assessment Analysis

1 The conclusions are drawn from

the model (mathematical

program), not from the problem!

2 An inadequate model typically

leads to false conclusions

3 The model must be

computationally tractable: its

analysis must be practical!

Dofasco:

“We find it useful to formulate the optimization problem even if we cannot

solve it...”

Benoˆt Chachuat (McMaster University) Formulating an Optimization Problem 4G03 3 / 31

Validity vs. Tractability

1 The validity of a model is the degree to which inferences drawn from

the model hold for the real system

2 The tractability of a model is the degree to which this model admits

convenient analysis – How much analysis is practical

Tradeoff:

Decision makers almost always confront a tradeoff between validity of

optimization models and their tractability to analysis

More complex

computations

Longer

of conditions

over wide range

Very accurate

Less complex

computations

Shorter

of conditions

Less accurate

over narrow range

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.