College aantekeningen

Summary Lecture Notes

1 keer verkocht

Instelling
Vrije Universiteit Amsterdam (VU)

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.

[Meer zien]

Voorbeeld 2 van de 11 pagina's

Bekijk voorbeeld

Geupload op 23 oktober 2022
Aantal pagina's 11
Geschreven in 2022/2023
Type College aantekeningen
Docent(en) Rene sitters
Bevat Chapter 1 - 5

Volgen

berendmarkhorst Lid sinds 8 jaar 92 documenten verkocht

€7,99

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

Combinatorial Optimization (E EORM COPT)

Berend Markhorst
October 23, 2022

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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.