College aantekeningen
Summary Lecture Notes
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
Voorbeeld 2 van de 11 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
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.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper berendmarkhorst. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €7,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 85169 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen