Please enable JavaScript.

Coggle requires JavaScript to display documents.

MAST90098 Approximation Algorithms and Heuristics 2018 SM2 UniMelb…

- - - - Loosely speaking, a tuple \((F,c)\) defining feasible solutions and cost function
      - Goal: find \(c(x^*) \leq c(x) \forall x \in F\)
      - 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)\)
    - - 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
  - - - Dynamic programming
      - Divide and conquer
  - - - 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\)
        
        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
        
        \(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
- - - - SAT
        
        Is a statement in CNF (conjunctions of disjunctions) satisfiable?
      - 2-SAT
        
        Restricted such that every clause has exactly two literals
        
        Solvable in polynomial time
      - 3-SAT
        
        Restricted such that every clause has exactly three literals
        
        NP complete
    - - Is there a perfect matching in bipartite graph
      - in P
    - - Does the graph contains a Hamiltonian Cycle
    - - 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
  - - - MST
        
        Algorithms
        
        Kruskals
        
        Keep adding minimum weight edge to tree without inducing cycle until fully connected
      - MIN-VCP
        
        Minimum vertex cover problem
        
        2-approximation algorithm
        
        Algorithm
        
        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.
        
        Proof of MIN-VCP 2-approximation
        
        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.
      - Travelling Salesman Problems
        
        Metric-TSP
        
        Satisfies triangle inequality
        
        Algorithm 1
        
        Algorithm
        
        Perform DFS and note order of vertices visited
        
        That order gives H the solution
        
        Find MST T
        
        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
        
        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^*)\)
        
        Euclidean TSP
        
        TSP
        
        Heuristic solutions|
        
        Greedy local search
        
        2-swaps
        
        3-swaps
        
        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
        
        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
        
        \(\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
        
        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|)
        
        Therefore there is no p(n) approximation of TSP (if \(P \neq NP\)) so TSP is in NPO(V)
      - MAX-MATCHING
        
        Find maximum matching in graph
      - WEIGHT-MIN-VCP
        
        Weighted minimum vertex cover problem
      - MAX-CUT
        
        Greedy local search algorithm
        
        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} \)
    - - MAX-CLIQUE
      - BIN-P
      - MAX-SAT
      - CHROMATIC NUMBER
    - - MS
        
        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
        
        Sort descending, add to shortest
      - SCP
        
        Set cover problem
        
        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|)\)
      - SKP
        
        Simple Knapsack
        
        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
      - KP
        
        Knapsack problem: maximize value subject to not exceeding capacity b
        
        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))\)
- - - - Arithmetic model: number of arithmetic operations performed
      - Bit model: Number of bit operations performed
      - Elementary model: number of elementary operations performed
    - - \(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
    - - \(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 \}\)
  - - - Polynomial: solvable by a deterministic TM in polynomial time
    - - NP-HARD
        
        Class of problems which are at least as hard as NP (but not necessarily in NP)
      - NP
        
        Characteristized by the existence of some certificate which can be verified in polynomial time i.e. certificate of a valid solutoin
        
        Includes P
        
        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
      - NP-complete
        
        Problems which are NP, and NP-hard - these are the hardest problems in NP
        
        To show that a problem is NP-hard, show it is in NP, then find an NP-complete problem which polynomially transforms to it
      - 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)
        
        If P != NP; cost bounded; integer valued, strongly NP hard ==> no exact polynomial time searchable neighbourhood. (Proof: otherwise GLS would solve in polynomial time)
      - 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\))
    - - Examples
        
        HALT: halting problem
    - - 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
  - - - 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 \)
    - - 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
- - - - Adapt the idea of local search in continuous spaces eg. gradient descent/Newton's method to combinatorial structures
    - - 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
      - 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 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)
    - - Algorithm
        
        Keep searching for improvements in local neighbourhoods until none found!
      - Parameters
        
        Initial start point
        
        Method of selecting point (if ambiguous)
        
        (?) Neighborhood function
    - - Always select best point in local neighrbouhood
    - - 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.
    - - 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
  - - - 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.
- - - - \(\epsilon_A(x) = \frac{|cost(A(x)) - Opt(x)|}{Opt(x)} \)
    - - \(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) \} \)
    - - 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\)
  - - - Algorithm which computes solution with relative error at most \(\epsilon\), but with time complexity \(Time_A(x,\epsilon^{-1})\) which is polynomial in \(|x|)\)
      - ==> relates to NPO(2)
    - - 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(1)