During the lectures, I made notes which I put in one document. Chapters 1 to 4 are fully covered, 5 partly, and 6 not at all. Reading them and practicing will prepare you well for the exam.
An optimization problem can be described by four properties: instance ,so-
lution, cost and goal. There are three levels of optimization (usually, it holds
that 1 → 2 → 3):
1. optimizing: find an optimal solution.
2. evaluating: what is the optimal value?
3. deciding: is OPT ≤ K?
In general, the running time gives an upper bound on the number of ’elemen-
tary’ operations done by the algorithm. An algorithm for some problems runs
in polynomial time if for every instance of the problem, the number of steps
taken by the algorithm is bounded by some polynomial in the input size.
Figure 1: Overview of all complexity classes discussed in this summary.
Definition 0.1. P is a complexity class that represents the set of all decision
problems that can be solved in polynomial time.
Definition 0.2. NP is a complexity class of all decision problems that can be
verified in polynomial time.
Definition 0.3. NP-complete is a complexity class which represents the set
of all problems X in NP for which it is possible to reduce any other NP problem
Y to X in polynomial time.
1
, NP-completeness does not prove that a problem has no efficient algorithm, but
it does give a strong argument.
Definition 0.4. NP-hard problems are at least as hard as the NP-complete
problems.
Note that an optimization problem is NP-hard if its decision version is NP-
complete.
Definition 0.5. A decision problem is strongly NP-complete if it is NP-
complete even when the numbers are polynomially bounded.
A decision problem A is reducable to a decision problem B if there is an
algorithm such that:
• for every I of A it produces an instance I ′ of B.
• it runs in polynomial time.
• I is yes-instance of A ⇐⇒ I ′ is yes-instance of B.
Figure 2: Some examples for P- and NP-complete problems.
1 An introduction to approximation algorithms
Definition 1.1. An α-approximation algorithm for an optimization prob-
lem is an polynomial-time algorithm that for all instances of the problem pro-
duces a solution for which the value is within a factor α of the value of an
optimal solution.
For an approximation algorithm, one needs to prove three things: (1) the run-
ning time is polynomial, (2) the solution is feasible; and (3) the value of the
solution is at most α times the optimal value.
Definition 1.2. The vertex cover of a graph is a set of vertices that includes
at least one endpoint of every edge of the graph.
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller berendmarkhorst. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.82. You're not tied to anything after your purchase.
