MAST90098 Approximation Algorithms and Heuristics 2018 SM2 UniMelb

Foundational ideas

Problems

Minimization problems

Loosely speaking, a tuple $(F,c)$ defining feasible solutions and cost function

Goal: find $c(x^*) \leq c(x) \forall x \in F$

Taxonomy of problems

Decision problems

Optimisation problems

Algorithms

Solves all instances of a given type of problem

Graph theory problems

MST

Algorithms

Kruskals

MIN-VCP

Travelling Salesman Problems

Metric-TSP

Euclidean TSP

TSP

Complexity classes

Time complexity

Ways of measuring

Arithmetic model: number of arithmetic operations performed

Bit model: Number of bit operations performed

Elementary model: number of elementary operations performed

Order

$f(n) \in O(g(n))$ if exists c s.t. $f(n) \leq c g(n)$

$f(n) \in \Theta(g(n)) $ if goes both ways

Complexity classes

NP stuff

EXP: exponential etc

Unsolvable

Examples

HALT: halting problem

NP-HARD

Characteristized by the existence of some certificate which can be verified in polynomial time i.e. certificate of a valid solutoin

Polynomial: solvable by a deterministic TM in polynomial time

Includes P

Class of problems which are at least as hard as NP (but not necessarily in NP)

NP-complete

Problems which are NP, and NP-hard - these are the hardest problems in NP

Any optimisation problem can be turned into a decision problem by posing: "is there a solution of at most $c$?"

MAX-MATCHING

Find maximum matching in graph

Misc. other problems

Transformations

Definition problem

To show that a problem is NP-hard, show it is in NP, then find an NP-complete problem which polynomially transforms to it

SAT

2-SAT

3-SAT

Restricted such that every clause has exactly three literals

Is a statement in CNF (conjunctions of disjunctions) satisfiable?

Restricted such that every clause has exactly two literals

Solvable in polynomial time

NP complete

Matching/marriage

Is there a perfect matching in bipartite graph

in P

3D MATCHING

click to edit

Strings and languages

Alphabet: finite set of symbols, $\Sigma$

Word: sequence of symbols from an alphabet

Language: Set of words from an alphabet, $L \subseteq \Sigma^*$

Given some alphabet defining the inputs (and possibly same alphabet for outputs), we can characterize a decision problem as a "language" - that is, the set of strings which is "accepts" i.e. produces "yes" for.

Set of all words: $\Sigma^*$

Decision problems

Formally, a triple $(L, W, \Sigma), L \subseteq W \subseteq \Sigma^* $. where $W$ defines the set of valid inputs and $L$ contains the outputs for which the decision is Yes

An algorithm $A$ is such that $A(x) = 1$ if $x \in L$ and $A(x) = 0)$ if $x \in W \setminus L$, and undefined otherwise

Formally, a triple $ U = (\Sigma, L, M, cost, goal) $ where $L \subset \Sigma^*, M : L \rightarrow 2^{\Sigma^*}, cost: (M \times L) \rightarrow \mathbb{R_+}, goal\in \{min,max \}$
$L$ is set of problem instances
$M$ is feasible solutions for any $x \in L$
$cost$ defines the cost of a solution in a problem instance

So a solution of $I \in L$ is $Opt_U(x) \in arg[goal]_x cost(x,I)$

Consistency: The algorithm always outputs a feasible solution, $A(x) \in M(x)$

Solves: the algorithm always finds a feasible optimal output eg. $A(x) \in Opt_U(x)$

Non-graph theory problems

Minimum vertex cover problem

SCP

Set cover problem

WEIGHT-MIN-VCP

Weighted minimum vertex cover problem

MAX-CLIQUE

MAX-CUT

Greedy local search algorithm

SKP

Simple Knapsack

Knapsack problem: maximize value subject to not exceeding capacity b

BIN-P

MAX-SAT

Formal definition

$Time_A(x)$ denotes time complexity of algorithm $A$ on instances $x \in I$

$Time_A(n) = \max_x \{ Time_A(x) | x \in I, |x| = n \}$

Formally, $L_1 \leq_p L_2$ if there exists polynomial time algorithm $A$ such that any instance $ x \in L_1, $ $x \in L_1 \Leftrightarrow A(x) \in L_2 $

Language $L$ is NP hard if fro any $U \in NP$, $U \leq_p L$

Examples

$SAT \leq_p CLIQUE$

$CLIQUE \leq_p VC$

Show that B is at least as hard as A by (polynomially time) transforming any (polynomially sized) instance of A into an instance of B such that the decision problems necessarily yield the same answer

For optimisation problems

NPO

Definition of NPO

1) Efficiently verify if string is an instance of the problem

2) Size of solutions is polynomial in instance size

3) Efficient verify if solution string is feasible

4) Cost of any solution is efficiently computable

Showing

Show that decision version of problem is easy/hard

Definition of PO

1) Is in NPO

2) There exists an algorithm which computes the optimal solution in polynomial time

Lemma PO

If $U \in PO$ then the threshold language of $U$ is in $P$

Converse: if threshold language of $U$ is NP-hard and $P \neq NP$, then $U \not\in PO $

Proof $SAT \leq_p CLIQUE$

Create vertex cluster for each clause with no internal arcs, were each vertex is a literal

Define arcs between vertices across clusters exactly when the literals are not negations of each other

$CLIQUE_M$ is Yes exactly when the statement in CNF is satisfiable

If $M$ clique exists necessarily it has exactly one vertex in each cluster. Select the literals corresponding to these vertices as the "true" literal assignments in the original CNF statement. So each clause in CNF has a true element, and, since none of the connective arcs link contradictory literals there is no contradiction in teh assignments. So teh CNF statement is satisfiable. Ditto for going the other way so biconditional

Heuristics

Definition

Strategies/algorithms which are consistent but with no mathematical guarantees of quality

Relaxing the necessity for optimality

If optimality bounds can be shown then it becomes an approximation algorithm

Local search heuristics

Population heuristics

Start with a group of solutions which interact to produce new solutions

The idea

Adapt the idea of local search in continuous spaces eg. gradient descent/Newton's method to combinatorial structures

Neighbourhoods

Definition of Neighbourhood

Function $N(x) \rightarrow 2^{M(x)} $

Reflexivity: $\alpha \in N(\alpha)$

Symmetry: $\beta \in N(\alpha) \rightarrow \alpha \in N(\beta)$

Connectivity/reachability: all points are a finite number of neighbourhood hops away from each other

Local Search Scheme

Algorithm

Keep searching for improvements in local neighbourhoods until none found!

Parameters

Initial start point

Method of selecting point (if ambiguous)

(?) Neighborhood function

Greedy Local Search (GLS)

Always select best point in local neighrbouhood

Heuristic solutions|

Greedy local search

2-swaps

3-swaps

Variable Depth Search (VDS) (Kerninghan Lin)

Establish some vector representation for problem

Each iteration, greedy select point in neighbourhood which alters at least one element, until all elements in vector modified exactly once

Choose best encountered solution along the way.

Simulated Annealing

Breakout of local minima by allowing worsening of solution with some probability

Choose random elements in neighbourhood

If new solution is not worse then accept

If solution is worse, then accept with probability $e^{-\frac{cost(\beta) - cost(\alpha)}{T}}$

So the greater the cost degrading, the low the probability; and the lower the temperature, the lower the probability

Parameters

Temperature update function

Neighbourhood

Genetic Algorithms

Key ideas

Fitness measure - basically cost function

Choose random parents (weighted by fitness) to produce children

Create child with crossover operation

Mutations can be applied

Advantage: can produce multiple high quality solutions

Algorithm

Randomly create initial population of P individuals, measure fitness

Choose k/2 sets of parents to produce children

Compute fitness of new individuals and choose best P

Produce children via cross over operation, add to population

Randomly apply mutation operation to each individual

Possibly improve individuals vial local search

Parameters

Population size: larger = better chance of global optimum. Some suggest 30 is a good size, or perhaps [n,2n] for input size n

Selection of initial population: can throw some high quality individuals in

Selection of parents: can simply weight them by their fitness value. Alternatively, can fix the best half, then randomly select others.

Probability of mutating: can be less than 1/100 for given element of individual. Or, could increase probability when individuals are too similar

Selection of new population: children completely replace parents or degree of preference for children or choose fittest individuals?

Stopping condition: if average fitness didn't change much then stop. Or fix number of generations in advance.

Pseudo-polynomial

Is exponential in the length of the input, but polynomial in the Max-Int and number of input integers

(eg. gets around problem where linear in max int which is technically exponential due to binary encoding)

Relevant to "Integer valued problems"

Formally, algorithms with complexity class $Time_A(x) = O(p(|x|, MaxInt(x)))$ for some polynomial $p$ where $MaxInt(x) \leq h(|x|)$ i.e. the max int is bounded polynomially by the size of the input

Broad classes of algorithms

Dynamic programming

Divide and conquer

Algorithms

Dynamical programming (optimal, pseudo-polynomial)

$k$ will range up to the sum of the costs

$I_i$ will range over the sequence of subsets of items, in order - so one subproblem for each subset $1...i$ of items

A tuple $(k, W_{ij},T_{ij})$ is computed for each $k$ where $W_{ij}$ is the minimum weight required to achieve exactly profit $k$ and $T_{ij}$ is (one possible) set of elements which achieves exactly that profit with that weight. If exactly profit $k$ can't be achieved then no triple generated

To compute this for $k$ from previous results, simply take each remaining element

Algorithm DPKP

Maintain a a set of triples generated

For each element in term $i =1...n$, add it to each triple and see what you get. If it exceeds $b$ then throw it out. Otherwise add it. Scan the final set for the best cost solution and you're done.

$SET_{i} = TRIPLE_{i-1} + \{ (k_{i-1}+c_i, W_{i-1,j} + w_i, T_{i-1,j} + \{ i \} | \text{triples before where addition of i doesn't exceed} b \} $

Add elements of $SET_i$ with unique $k$ and minimal weights

Proof: DPKP Pseudopolynomial time

Each TRIPLE contains only unique values of k which is bounded by $k \leq \sum_i c_i$ so $|TRIPLE_i| \leq \sum_i c_i \leq n \cdot MaxInt(I)$

We have to compute $n-1$ subproblems

So complexity is $O(n \cdot n\cdot MaxInt(I)) = O(n^2 MaxInt(I))$

Strongly NP-HARD

The h-value-bounded subproblem for some non-decreasing h(n) is the subproblem where the maximum integer is bounded by h(|x|) so $MaxInt(x) \leq h(|x|), h : \mathbb{N} \rightarrow \mathbb{N} $

Sub-problem of U is called Value(h)-U

Problem $U$ is strongly NP-hard if for some polynomial $p$, the value bounded subproblem $Value(p)-U$ is NP-hard

In other words. even when the integer values in the problem are "reasonable" and not "too large" (i.e. polynomial in the size of the input) then it's still NP hard.

This means that the NP-hardness is not stemming from the silly thing about numbers having log length in their value... it's something more fundamental in the problem itself.

if P != NP then Strongly NP-hard ==> No pseudopolynomial time algorithm (Proof: otherwise, for small integers, solvable in polynomial time)

TSP is strongly NP hard

Proof that TSP is strongly NP hard

Reduction from HC problem

Create graph with edge cost 1 if in HC, edge cost 2 otherwise. Then, MaxInt(x) <= 2 which is polynomial in size of input. If Decision version of TSP had polynomial time algorithm then HC would have one. But HC is NP-complete, so dammit.

Since decision version of polynomially bounded TSP is NP-hard, TSP is strongly NPO hard

NOTE Works for metric TSP as well since satisfies triangle inequality by construction

Definition of Exact neighbourhood

Is exact neighbourhood if every local optimum is a global optimum

Definition of Polynomial Time Searchable

Neighbourhood is polynomial time searchable if there exists an algorithm polynomial in |x| which finds an optimum in the neighbourhood

If P != NP; cost bounded; integer valued, strongly NP hard ==> no exact polynomial time searchable neighbourhood. (Proof: otherwise GLS would solve in polynomial time)

if cost bounded and strongly NP-hard then no exact polynomial time searchable neighbourhood

Another way: If U in NPO, and P != NP and the sub-optimality decision problem (deciding if solution is suboptimal) is NP-hard, then does not have exact polynomial time searchable algorithm. (Proof: because if it does have such an algorithm they we could decide the SUBOPT problem in polynomial time)

Does the graph contains a Hamiltonian Cycle

RHC

Given a Hamiltonian path P, which cannot be extended to a HC, does the graph contain a HC

$HC \leq_p RHC$

Proof of $HC \leq_p RHC$

Gadget needed: diamond subgraph replaces each vertex, such that if the graph contains a HC then all the vertices are traversed NS or EW, but not a mix

So take the original grpah and replace everything like that...connect the EW ones according to original arcs, and then create a HP by connecting the NS ones according to some arbitrary vertex ordering.

So we know the graph contains a HP. If finding a HC as polynomially solvable then we would do so and find a HC which necessarily must run EW mode. This solution cna be transformed into HC original

However HC is NP-complete, so this is impossible. So RHC is NP-hard

SUBOPT-TSP

$RHC \leq_p SUBOPT-TSP$

Proof that $ RHC \leq_p SUBOPTTSP$

Create complete graph where edges in original graph have cost 1 and others have cost 2. Since HP in original cannot be extended to a HC then by adding the final connecting edge it has cost n+1

If the SUBOPT-TSP problem was solvable in polynomial time then we solve it. If the answer is Yes then there exists a HC of cost (n), which necessarily uses edges in the original graph, so HC is Yes. Otherise the answer is No.

However RHC is NP-hard so that can't be the case, so SUBOPTTSP is NP hard

Since SUBOPT-TSP is NP-hard, TSP does not contain any exact, polynomial time searchable neighbourhood (which sucks)

Pathological case of TSP

For any $k \geq 2$ there is a nasty pasty TSP instance which pretty much kills any $3k$ size neighbourhood... it will be $(K_{8k}, c_M)$

Graph with k diamonds... (just make others extremely large cost). So a HC will either be EW or NS mode only.

Connect HC in EW mode with cost 1 so this has cost 8k

Connect all other EW modes with cost 2M so they all have cost at least $2M \geq 2^{8k+1}$

Make all NS edges from N1 cost M and all other NS edges cost 0

So example one optimal; all NS ones will have cost M+5k, and all EW ones at least 2M

Approximation algorithms

Key ideas

Relative error of algorithm $A$ consistent for problem $U$

$\epsilon_A(x) = \frac{|cost(A(x)) - Opt(x)|}{Opt(x)} $

Approximation ratio $R_A(x)$ for problem $U$

$R_A(x) = \max \Big\{ \frac{cost(A(x))}{Opt(x)}, \frac{Opt(x)}{cost(A(x)} \Big\} $

In other words it's the ratio $\geq 1$ depending on min or max problem

For problem size $n$ the approximation ratio is defined as:
$R_A(n) = \max \{ R_A(x) | x \in L_U(n) \} $

Approximation algorithm

Algorithm $A$ is a $\delta$-approximation algorithm for problem $U$ if $R_A(x) \leq \delta, \forall x \in I_U$

Algorithm $A$ is a $f(n)$-approximation algorithm if $R_A(n) \leq f(n)$ for all $n$

Makespan scheduling problem

Greedy Algorithm

GMS 2-Approximation Proof

Split $n\leq m$ (trivial), $k \leq m$ (trivial) and $k > m$

Let $T_l$ be a longest queue, $k$ be largest index of job in queue

Since always add to shortest queue, all other queues were at least $cost(GMS(I)) - p_k$ when $p_k$ added to $T_l$ so $Opt(I) \geq cost(GMS(I)) - p_k$

$ \frac{cost(GMS(I)) - Opt(I)}{Opt(I)} \leq \frac{p_k}{Opt(I)} \leq \frac{\sum_{i=1}^k p_i / k}{ \sum_{i=1}^m p_i / m} \leq \frac{m}{k} < 1 $

So $\epsilon_{GMS}(I) \leq 1$ so $R_{GMS}(I) \leq 2$ BANG

Approximation schemes

Def: Polynomial time approximation scheme PTAS

Algorithm which computes solution with relative error at most $\epsilon$, but with time complexity $Time_A(x,\epsilon^{-1})$ which is polynomial in $|x|)$

Can sometimes do even better that $\delta$-approximation - make the relative error a tunable parameter!

Def: Fully polynomial time approximation scheme FPTAS

Algorithm which computes solution with relative error at most $\epsilon$ but with time complexity $Time_A(x,\epsilon^{-1})$ polynomial in both $|x|,\epsilon^{-1}$

==> relates to NPO(2)

==> relates to NPO(1)

Def: NPO

NPO(1)

Contains all optimization problems for which there is a FPTAS

NPO(2)

Contains all optimization problems for which there is a PTAS

NPO(3)

There is no PTAS but there is a a $\delta$-approximation which is a tight lower bound for constant approximation factors. (Assuming $P \neq NP$)

NPO(4)

There is no $\delta$-approximation but there is a $f(n)$-approximation where $f(n)$ is a polylogarithmic function (i.e. polynomial of logarithm) (Assuming $P \neq NP$)

NPO(5)

You're screwed. If there is a $f(n)$-approximation then it is not bounded by any polylogarithmic function i.e. it's a bad function. (Assuming $P \neq NP$)

2-approximation algorithm

Algorithm

Proof of MIN-VCP 2-approximation

Find maximal matching $M$

Take all adjacent vertices as the vertex cover

Must be a vertex cover: Suppose some edge was not covered. Then that could be added to the matching $M$. But we found a maximal matching. So necessarily all edges are covered.

Since the cardinality of every (maximal) matching is a lower bound on the cardinality of every vertex cover, and we have double the number of vertices, it is a $2$-appromixation with relative error at most 1.

Greedy/Naive Set Cover algorithm

Just keep adding sets such that the number of newly covered elements is maximal i.e. greedy; until all covered

Proof: Naive SCP is $Har(max|S|)$-approximation + $ln(n)$-approximation

Let $S_i^*$ be set of newly covered elements in i iteration
Let $Weight_C(x) = 1/|S_i^*|$ if $x$ first covered in iteration i
Let \cov_i(S)\) be number of uncovered elements of S after i iteration

NOTE: $cov_{i-1}(S) \geq cov_i(S)$
$|S_{i-1}^*| \geq |S_i^*|$

$|C| = \sum_{x \in X} Weight_C(x) \leq \sum_{S \in C^*} \sum_{x \in S} Weight_C(x) \leq |C^*| Har(max(|S|, S \in F))$

$\sum_{x \in S} Weight_C(x) = \sum_{i=1}^k (cov_{i-1}(S) - cov_{i}(S))\frac{1}{|S_i^*} \leq \sum_{i=1}^k (cov_{i-1}(S) - cov_{i}(S))\frac{1}{cov_i(S)} = \sum_{i=1}^k (1 - \frac{a}{b}) \leq \sum_{i=1}^k (Har(cov_{i-1}(S)) - Har(cov_i(S))) = Har(cov_0(S)) - Har(cov_k(S)) = Har(|S|)$

Keep moving between partitions until no local change improves it

Proof: MAX-CUT 2 approximation

$c = \frac{\sum_{v \in V} c(v)}{2} \geq \frac{\sum_{v \in V} deg(v)/2}{2} = \frac{|E|}{2} \geq \frac{|C^*|}{2} $

Greedy

Order items, add in term if fit

Greedy extension

consider every $k = \left\lceil 1/\epsilon \right\rceil$ subset and do greedy from there

Is PTAS for SKP

Satisfies triangle inequality

Algorithm 1

Algorithm

Perform DFS and note order of vertices visited

That order gives H the solution

Proof: Metric TSP 2-approximation

$cost(H) \leq 2 cost(T) \leq 2 cost(H^*)$

Proof: 2-approximation is tight

Graph where "internal" are 1 and "external" are 2

Algorithm bay produce (2n-2)/(n+1) -->2

Find MST T

Christofides algorithm

Algorithm

Find MST T

Find minimum weight perfect matching M among S = odd degree vertices

Find eulerian path w in T+M

Create shortcutted path H of w

Proof: Christofides 3/2 approximation

Let $S = \{v_1,v_2,...v_{2m} \}$ be the set of odd degree vertices in $T$, ordered by order in $H^*$
Let $M$ be minimum perfect matching used
Let $M_1$ and $M_2$ be matchings on $S$ formed by alternating the order in $H*$

Note that $2cost(M) \leq cost(M_1) + cost(M_2) \leq cost(H^*)$

So $cost(H) \leq cost(\omega) = cost(T) + cost(M) \leq cost(H^*) + \frac12 cost(H^*) = \frac32 cost(H^*)$

$\Delta$-TSP${}_r$

Relaxed triangle inequality by $r$

So $cost(u,v) \leq (1+r)(cost(u,w) + cost(w,v))$

d-App-TSP

Problem of finding a solution to TSP such that $cost(H) \leq d \cdot cost(H^*)$

Proof: $HC \leq_p$ d-App-TSP

Therefore there is no p(n) approximation of TSP (if $P \neq NP$) so TSP is in NPO(V)

Create complete graph where original edges have cost 1 and extra edges have cost $(d-1)|V|+2$

So if no HC then every tour has at least
\( |V| - 1 + (d-1)|V| + 2 = d|V| + 1 > d|V|)

Non-deterministic polynomial: solvable by a non-deterministic TM i.e. one which finds the solution along a path of polynomial length, as if it was exploring all paths simultaneously

CHROMATIC NUMBER

Keep adding minimum weight edge to tree without inducing cycle until fully connected

Sort descending, add to shortest