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
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
