Problems and solutions

Feasible:

A feasible solution to a problem is legal with regards to the requirements of the problem or the problem's environment. A feasible solution to the knapsack problem could be any subset of items whose total weight does not exceed the maximum allowed weight.

Graphs

Assume we have a graph $G = (V, E)$.

• $V$ is the set of the graph's vertices/nodes.
  • $|V|$ is the number of vertices.
  • The degree of a vertex is the number of edges directly connected to it/with it as one of its endpoints.
• $E$ is the set of the graph's edges/arcs.
  • $|E|$ is the number of edges.
  • An edge can be defined on the form $(i, j)$, where $i$ and $j$ are vertices of the graph. I.e. $(i, j) \in E$, $i \in V$, $j \in V$.
  • An edge $e$ is said to be incident on a vertex $v$ if one of its endpoints is $v$.
• A path between two nodes is a series of edges that lead from one node to another. A single edge is a path. "$(i, j), (j, k)$" is a path.

A graph $G$ is complete if there is an edge from each and every vertex to all the other vertices in the graph: iff for every pair of vertices $i$ and $j$ in $V$, there exists an edge $(i, j)$ in $E$. A complete graph has $\sum_{i=1}^{i = |V|-1}i = \frac{n(n-1)}{2}$ edges.

A directed graph $G$ is strongly connected there exists a path from each and every vertex to all other vertices in the graph. That is, if it is possible to get from any node $i$ in the graph to any other node $j$ in the graph. If $G$ is undirected, but the rest of the description still matches then it's just connected.

Two vertices $i$ and $j$ in a graph are adjacent if there exists an edge $(i, j)$ in the graph. So in a complete graph, all vertices are adjacent.

A graph can be described as metric if for any vertices in the graph, the length of any path of size $\geq 2$ between $i$, $j \in V$ is greater than or equal to the length of a path of size $1$ between the same two vertices. In other words, the direct route from A to C is not longer than a route from A to B to C. I.e., $i$, $j$, $k \in V$, $d_{ik} \leq d_{ij} + d_{jk}$. Typically metric is used to describe a problem instance (such as metric instances of TSP).

A graph is Eulerian if it contains an eulerian path. An eulerian path is a path that visits each edge in the graph exactly once. A graph is eulerian if and only if it is strongly connected and each node has an even degree.

A perfect matching of a set of nodes is a collection of edges that contain each node in the set exactly once. Suppose that $O = \bigcup_{i=1}^{k} v_i$. A perfect matching of $O$ looks something like this: $(v_1, v_2), (v_3, v_4), ..., (v_{k-1}, v_k)$.

A connected component of an undirected graph $G$ (sometimes just "component") is an isolated, connected subgraph $S \subset G$.

Inequalities

$$A = B \implies (A \geq B) \vee (A \leq B)$$ If A is equal to B, that's the same as saying that A is less than or equal to B and also greater than or equal to B. If we know that $A = B$, we can pick and use either inequality if it is convenient, like if we need it to prove something.

$$A \geq B \geq C \implies A \geq C$$ Yeah, transitivity is still a thing.

Sums

If $\sum_{i=1}^{k}x_{i} = n$, where $x_{i} \geq 0$, then we can assume that there exists some $x_{i}$ whose value is greater than the average value of the elements in the sum, $\frac{n}{k}$. Again, with more symbols: $$\sum_{i=1}^{k}x_{i} = n \implies \exists i : x_{i} \geq \frac{n}{k}$$

It also implies that there is some $x_{j}$, $j \neq i$ whose value is less than the average value. You'd be surprised how often this pops up.

Say you have some sum $\sum_{i=1}^{k}x_{i} = n$. We know that, for some $i$, $x_i \geq \frac{n}{k}$, right? Now let's assume that $x_k$ is the element in the sum with the highest value. If we subtract this element from the sum, what can we say about the sum? Since $x_k$ is the highest valued element of the sum, its value must be greater than or equal to $\frac{n}{k}$. If $A, B \geq 0$ and we subtract A from B, and we know that A has some minimum value $A_{min}$, then $(B-A) \leq (B - A_{min})$, because $A \geq A_{min}$.

$$\begin{equation} \begin{split} \sum_{i=1}^{k-1}x_{i} & \leq \sum_{i=1}^{k}x_i - \frac{1}{k} \sum_{i=1}^{k}x_i & \leq \sum_{i=1}^{k}x_i \\ & \leq (1-\frac{1}{k}) \sum_{i=1}^{k}x_i & \leq \sum_{i=1}^{k} x_i \end{split} \end{equation}$$

"In what scenario would this ever be useful", one wonders. Oh, who knows, really. Like, if we knew that $n \leq \alpha \cdot OPT$ for some problem then we could use this to show that $n(1-\frac{1}{k}) \leq (1-\frac{1}{k}) \cdot \alpha \cdot OPT$ (because transitivity is still a thing). Which is done on page 195 of TDoAA for the multiway cut problem and the proposed minimum-cut-based algorithm.

P

P contains those decision problems that can be solved in polynomial time. Given an instance of a problem in P, it is theoretically possible to produce a solution in polynomial time. However, a problem being in P does not imply that a concrete algorithm is known that solves it in polynomial time, only that such an algorithm exists. See Polynomial-recognition of the Robertson-Seymour theorem on Wikipedia for an example of this.

All problems in P are also in NP.

NP (nondeterministic polynomial time)

The class NP contains those decision problems for which the instances where the answer is "yes" can be verified in polynomial time.

The decision variant of the knapsack problem is in NP. It asks if there exists some combination of items whose total value is greater than or equal to $C$ and whose total weight is less than $B$. Given a combination of items, we can easily verify if their total value and total weight meet the requirements by summing each item's value and weight and comparing the result to $C$ and $B$.

NP-Complete

A problem $B$ is NP-complete if $B$ is in NP, and for every problem $A$ in NP, there is a polynomial-time reduction from $A$ to $B$.

A polynomial-time reduction from $A$ to $B$ takes as its input an instance of $A$ and produces an instance of $B$ in polynomial time. The produced instance of $B$ has the property that it is a "Yes" instance of $B$ if and only if a "Yes" instance of $A$ was input.

We can reduce an instance of the Hamiltonian cycle decision problem ("Does this undirected graph $G = (V, E)$ have a Hamiltonian cycle?"), which is NP-Complete, to an instance of the Traveling Salesman Problem (TSP). TSP takes as its input a complete graph $G'$. We can transform $G$ to $G'$ in polynomial time: set the cost of each edge in $G'$ that is also in $G$ to 1. Add edges to $G'$ until it is complete and set the cost of these to $|V|$. Now, if we have some algorithm that solves instances of TSP by producing the shortest tour possible in the graph, we can use this to determine whether or not $G$ has a Hamiltonian cycle: if the cost of the tour returned by our TSP algorithm is equal to $|V|$ then there exists a Hamiltonian cycle in $G$. However if the cost of the tour returned by our TSP algorithm is greater than $|V|$, which it will be if it contains an edge not in $G$, there is no Hamiltonian cycle in $G$. The instance of the Hamiltonian cycle problem has been reduced to an instance of TSP where we ask if there exists some tour of cost $c \leq |V|$. $% Example taken from pg 36 of TDoAA.$

NP-Hard

"NP-hard problems are at least as hard as the hardest problems in NP." A problem $A$ is NP-hard if there is a polynomial-time algorithm for an NP-complete problem $B$ when the algorithm has oracle access to $A$. If an algorithm has "oracle access to $A$", it can solve an instance of $A$ in a single instruction that is completed in polynomial time. The term "NP-hard" can be applied to either optimization and decision problems.

The optimization version of the knapsack problem is NP-hard: Given an instance of the decision version of the knapsack problem, we just check if the value of the optimal solution is at least the value which the decision version asks about.

Integer Program (IP)

Synonyms: Integer Linear Program (ILP)

An integer program is like a linear program except that the decision variables are restricted to being integers rather than real numbers.

Integer programs are NP-hard.

0-1 Integer Linear Program (01ILP)

Synonyms: Binary LP, 01LP, Binary ILP.

An integer program is like a linear program except that the decision variables are restricted to being either 0 or 1.

In the LP formulation of the knapsack problem above we would have to replace the restraint $x_{j} \geq 0$ with $x_{j} \in \{0, 1\}$.

Alphabet

Any non-empty, finite set is called an alphabet. Every element of an alphabet $\Sigma$ is called a symbol of $\Sigma$.

Example alphabets:

• $\Sigma_{\text{bool}} = \left\{0, 1\right\}$
• $\Sigma_{\text{latin}} = \left\{a, b, c, d, e , ... , z \right\}$
• $\Sigma_{\text{logic}} = \left\{0, 1, (,), \wedge, \vee, \neg, x \right\}$

Word

Let $\Sigma$ be an alphabet. A word over $\Sigma$ is any finite sequence of symbols of $\Sigma$. The empty word $\Lambda$ is the only word consisting of zero symbols. The set of all words over the alphabet $\Sigma$ is denoted by $\Sigma^*$.

Language

Let $\Sigma$ be an alphabet. Every set $L \subseteq \Sigma^*$ is called a language over $\Sigma$.

$\text{Time}_A(x)$ and $\text{Space}_A(x)$

Let $\Sigma_{\text{input}}$ and $\Sigma_{\text{output}}$ be alphabets. Let $A$ be an algorithm that realizes a mapping from $\Sigma_{\text{input}}^*$ to $\Sigma_{\text{output}}^*$. For every $x \in\Sigma_{\text{input}}^*$, $\text{Time}_A(x)$ denotes the time complexity of the computation $A$ on the input $x$, and $\text{Space}_A(x)$ denotes the space complexity of the computation $A$ on $x$.

Time complexity of an algorithm

Let $\Sigma_{\text{input}}$ and $\Sigma_{\text{output}}$ be two alphabets. Let $A$ be an algorithm that computes a mapping from $\Sigma_{\text{input}}^*$ to $\Sigma_{\text{output}}^*$. The worst case time complexity of $A$ is a function $\text{Time}_A: (N - \left\{ {0} \right\} ) \to N$ defined by $\text{Time}_A(n) = \text{max}\left\{\text{Time}_A(x) | x \in \Sigma_{\text{input_n}}\right\}$ for every positive integer $n$.

Time

Space

Uniform-cost measurement

Every machine operation is assigned a single constant time cost. This means that an addition between two integers, as an example, is assumed to take the same amount of time regardless of the size of the integers. This is often the case in practical systems for sensibly sized integers. This is the cost measurement used throughout Hromkovič.

Logarithmic-cost measurement

Cost is assigned to the number of bits involved in each operation. This is more cumbersome to use, and is therefore usually only applied when necessary.

Famous NP-complete problems

This is a list of important or otherwise famous NP-complete problems, which are probably nice to know by heart, as they assumed to be known, and can therefore be used freely in proofs.

Example: Primality test

Consider the decision problem of whether a number $n$ is a prime number. The naïve approach of checking whether each number from $2$ to $\sqrt{n}$ evenly divides $n$ is sub-linear in the value of $n$, but exponential in the size of $n$.

Fixed-parameter polynomial time algorithms

A parametrized problem is a language $L \subseteq \Sigma^{*} \times \mathbb{N}$. The second component is called the parameter of the problem. A parametrized problem $L$ is fixed-parameter tractable if the question $(x,k) \in? L$ can be decided in running time $f(k) \dot |x|^{O(1)}$, where $f$ is an arbitrary function depending only on $k$. In such cases, it is often practical to fix the parameter $k$ to a small(ish) constant.

Polynomial-time approximation scheme (PTAS)

A polynomial-time approximation algorithm, $A$, is a PTAS if the approximation error is bounded for each input, and $\text{Time}_A(x, \frac{1}{\text{error}})$ is polynomial in $|x|$.

Fully polynomial-time approximation scheme (FPTAS)

An PTAS is FPTAS is it is polynomial in $|x|$ and $\frac{1}{\text{error}}$.

Straight up regular local search

For your basic local search you need the following:

• A neighbor graph showing the relation between neighboring solution candidates
• A fitness function evaluating candidate solutions
• Good luck

Straight up regular local search will quickly find a local optimum from where the search is started, but does not guarantee finding a global maximum, nor does it know if a global maximum has been found.

There are several ways of selecting a neighbor to follow when doing a local search, two of which are first improvement and steepest descent. Steepest descent evaluates all neighbors, and selects the best neighbor. First improvement selects the first neighbor which is better than the current solution candidate. First improvement is often faster to calculate, but Steepest descent usually converges faster to a local optimum.

Variable-depth search

Variable depth search provides a nice compromise between first improvement and steepest descent. In variable depth search, changed variables in a solution are locked, preventing their further modification in that branch. Kernighan-Lin is the canonical example of variable-depth search.

Simulated annealing

Simulated annealing introduces probability and randomness to which neighbor is selected. This reduces the chance of getting stuck in a non-global local maximum.

Tabu search

Tabu search marks certain solutions as tabu after processing, and never revisits them. This is often done on an LRU or LFU basis. A common implementation is a search which remembers the last $k$ visited candidate solutions, and avoids revisiting them.

Tabu search prevents a candidate solution to be considered repeatedly, getting the search stuck in plataus.

Randomized Tabu search

Like regular Tabu, but randomized (or so the name seems to suggest).

Intensification vs Diversification

Intensification is the intense search of a relatively small area - that is, the exploitation of a discovery of a good area. Diversification is looking at many diverse regions, exploring uncharted territories. Intensification is often quicker at reaching a local optimum, but diversification is better geared towards discovering global optimums.

Initialization

Initialization is the step of creating a starting population $P = \left\{a_1, a_2, ..., a_k\right\}$ which becomes the first generation of the algorithm. Random generation is a good way of doing this, but there are other approaches.

Selection

Selection is the step of selecting $ n \le k $ indivudials from the population, on which genetic operators will be applied. A good selection strategy is crucial for success in a genetic algorithm. Using the fitness value to select the $n$ best individuals from the population is common ('survival of the fittest'), and throwing in some randomness as well is usually a good move.

Genetic operators

Genetic operators work on individuals to make new, different individuals.

Termination

Integer programming (IP)

IP is linear programming where the variables can only take integer values. IP is NP-hard.

Binary linear programming (01LP)

01LP is linear programming where the variables can only take 0 or 1 as values. 01LP is NP-hard.

Relaxation to LP

Many interesting optimizaition problems with useful solutions are easily reduced to IP or 01LP. Because IP and 01LP are both NP-hard, and LP is P, relaxing problems to LP is a good idea when possible. Here is how:

1. Express an optimization problem $U$ as an instance $I$ of IP or 01LP.
2. Pretend that $I$ is an instance of LP, and find a solution $a$.
3. Use $a$ to solve the original problem.

Easy, right?

Parametrized complexity applications

So you have an NP-hard problem. Nice. And difficult. So difficult that it is impossible to solve in polynomial time (unless $P = NP$). Anyway, here is a general plan that might help:

1. Define a subproblem mechanism for defining subproblems according to their supposed subproblem difficulty.
2. Use this mechanism to define a class of easy subproblems.
3. Define a requirement for an algorithm to have a nice time complexity with respect to the subproblem difficulty, in such a way that a nice algorthm can solve an easy problem in polynomial time.
4. Then, either:
5. design a nice algorithm, and prove that is nice, or
6. prove that it is impossible to design a nice algorithm, unless $P = NP$.

Look at these categories for ideas for the different subproblem mechanisms, proofs, etc:

Local search algorithm design

1. Make sure you have an optimization problem and not a decision problem.

2. Define a neighborhood function. This function maps for an input instance x each feasible solution a for x to other feasible solutions for x called the neighbors of a. Typically, neighboring solutions differ only by some small modification.

3. Start the search anywhere you want. Randomly choosing some place is a nice strategy.

4. Repeat the following: go to best neighbor (or don't, if all neighbors suck, comparitively).

5. In the case where all neighbors suck, give up. You have a local optimum and the search is done.

Genetic algorithm template

1. Randomly generate a population of individuals.
2. Apply a fitness function to calculate a fitness score for each individual in the current generation.
3. Select individuals for reproduction based on fitness and a little randomness.
4. Apply crossover and mutation to the selected individuals to produce the next generation.
5. Stop whenever you feel like it.

Proving that a decision problem is undecidable

You have a decision problem E which you suspect is undecidable. Unfortunately, you need proof. A general method is: 1. Find a different decision problem H which is known to be undecidable. I recommend the halting problem. 2. Suppose a decider R decides E. Define a decider S that decides H using R. 3. If R exists, S can solve H. However H cannot be solved. Therefore, R cannot exist.

The Primal-Dual schema

(taken from cmu.edu)

We typically devise algorithms for minimization problems in the following way:

1. Write down an LP relaxation of the problem, and find its dual. Try to find some intuitive meaning for the dual variables.

2. Start with vectors x = 0, y = 0, which will be dual feasible, but primal infeasible.

3. Until the primal is feasible:

   1. increase the dual values $y_i$ in some controlled fashion until some dual constraint(s) goes tight (i.e. until $sum_i y_i * a_ij = c_j$ for some $j$), while always maintaining the deal feasibility of y.
   2. Select some subset of the tight dual constraints, and increase the primal variable corresponding to them by an integral amount.

4. For the analysis, prove that the output pair of vectors (x,y) satisfies $c^{[trans]} * x <= \rho * y^{[trans]} * b$ for as small a value of rho as possible. Keep this goal in mind when deciding how to raise the dual and primal variables.

Christofides' algorithm

Use this to approximate the TSP $G = (V,w)$ with $\rho = 1.5$, where the edge weights satisfy the triangle inequality.

1. Create the MST $T$ of $G$.
2. Let $O$ be the set of vertices with odd degree in $T$ and find a minimal matching $M$ in the complete graph over $O$.
3. Combine the edges of $M$ and $T$ to form a multigraph $H$.
4. Form an eulerian circuit in $H$.
5. Make the circuit found in previous step Hamiltonian by skipping visited nodes ('shortcutting').

You now have an approximation of TSP with $\rho = 1.5$. Why does this approximate TSP with $\rho = 1.5$, you ask? Well:

Converting problems

2013, spring

This year (2013), the curriculum is chapters 3, 4 and 6, except 4.3.6-4.5, of Hromkovi$\check{c}$'s Algorithmics for hard problems.

The topics covered are:

• Deterministic approaches
  • Pseudo-polynomial-time algorithms
  • Parametrized complexity
  • Branch and bound
  • Lowering worst case complexity of exponential algorithms
  • Local serach
  • Relaxation to linear programming
• Approximation algorithms
  • Fundamentals: Stability, Dual approximation etc
  • Algorithm design: lots of approximations for known hard problems
• Heuristics
  • Simulated annealing
  • Tabu search
  • Genetic algorithms