Unit 5: Backtracking and Approximation Algorithms

1. Introduction to Backtracking

Backtracking is a systematic method to iterate through all the possible configurations of a search space. It is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options.

• State-Space Tree: The search space is represented as a tree. The root represents the initial state, and leaves represent the final states (solutions or dead ends).
• Depth-First Search (DFS): Backtracking traverses the state-space tree using DFS.
• Bounding Function / Pruning: As the tree is explored, the algorithm checks if the current node can lead to a valid solution. If it cannot, the algorithm "backtracks" (returns to the parent node) and explores other branches, pruning the dead-end subtree.

1.1 The n-Queens Problem

Problem Statement: Place non-attacking queens on an chessboard. Two queens are attacking each other if they share the same row, column, or diagonal.

Backtracking Approach:

1. Place queens column by column (or row by row).
2. For column , try placing a queen in each row (from 1 to ).
3. Constraint Check: Check if placing a queen at is safe (no queen in the same row, column, or diagonals).
4. If safe, mark the position and recursively place the queen in the column.
5. If placing the queen at does not lead to a solution, unmark the position (backtrack) and try the next row.

Time Complexity: in the worst case, though pruning significantly reduces actual execution time.

1.2 Hamiltonian Circuit Problem

Problem Statement: Given an undirected graph , find a cycle that visits every vertex exactly once and returns to the starting vertex.

Backtracking Approach:

1. Start at an arbitrary vertex (e.g., vertex 0).
2. Maintain an array path[] to store the sequence of vertices.
3. At each step, try adding a new vertex to path[].
4. Constraint Check:
   • The new vertex must have an edge connecting it to the previously added vertex.
   • The new vertex must not already be in path[].
5. If valid, add the vertex and recurse.
6. If the path contains all vertices, check if there is an edge from the last vertex back to the first vertex. If yes, a Hamiltonian circuit is found.
7. If not, remove the vertex (backtrack) and try another adjacent vertex.

1.3 Subset-Sum Problem

Problem Statement: Given a set of non-negative integers and a target weight , find a subset of whose elements sum to exactly .

Backtracking Approach:

1. Sort the set in ascending order (optional but highly recommended for efficient pruning).
2. Traverse the state-space tree where each node represents the inclusion or exclusion of the current element .
3. Constraint Check / Pruning:
   • If current sum + , prune the branch (since the array is sorted, subsequent elements will also exceed ).
   • If current sum + sum of all remaining elements , prune the branch (it's impossible to reach ).
4. If current sum , a solution is found.

2. Introduction to Branch-and-Bound

Branch-and-Bound (B&B) is an algorithm design paradigm generally used for solving combinatorial optimization problems. Like backtracking, it uses a state-space tree, but with key differences:

• Search Strategy: B&B typically uses Breadth-First Search (BFS) or Best-First Search (using a Priority Queue), rather than strictly DFS.
• Optimization: It is used for optimization problems (finding minimum or maximum cost), whereas backtracking is usually for decision/enumeration problems.
• Bounds: It calculates a bound (lower bound for minimization, upper bound for maximization) at each node to determine whether the node can lead to a better solution than the current best. If the bound is worse than the current best solution, the node is pruned.

2.1 Assignment Problem

Problem Statement: Assign jobs to workers such that the total cost of assignment is minimized. Given an cost matrix where is the cost of assigning worker to job .

Branch-and-Bound Approach:

1. State Space Tree: Level represents assigning a job to worker .
2. Lower Bound Calculation: The minimum possible cost at a node can be estimated by taking the cost of the current assignments plus the minimum element of each unassigned worker's row.
3. Exploration: Use Best-First Search. Generate all possible job assignments for the next worker. Calculate the lower bound for each.
4. Expand the node with the minimum lower bound.
5. If a leaf node is reached and its cost is less than the current optimal cost, update the optimal cost.

2.2 0/1 Knapsack Problem

Problem Statement: Given items with specific weights and values, and a knapsack of capacity , maximize the total value without exceeding the capacity. Fractional items are not allowed.

Branch-and-Bound Approach:

1. Sort items by value-to-weight ratio in descending order.
2. Upper Bound Calculation: To calculate the maximum possible profit for a node, take the current profit and add the profit of the remaining items. If an item doesn't completely fit, take a fraction of it (this is the fractional knapsack greedy approach, which provides a strict upper bound).
3. Exploration: Generate two children for each item (Include item, Exclude item).
4. If the upper bound of a node is less than the current maximum profit (max_profit), prune the node.
5. Update max_profit whenever a valid combination with a higher profit is found.

2.3 Traveling Salesman Problem (TSP)

Problem Statement: Given a set of cities and the distances between them, find the shortest possible route that visits every city exactly once and returns to the origin city.

Branch-and-Bound Approach (Cost Matrix Reduction):

1. Row & Column Reduction: Reduce the cost matrix so that every row and column has at least one zero. The sum of the subtracted minimums forms the initial lower bound.
2. Branching: From city , consider all unvisited cities .
3. Bounding: The cost of the child node is:
   Cost(Parent) + Cost[i][j] (from reduced matrix of parent) + Cost of reducing the new child matrix.
   When transitioning from , set row and column to infinity, and set (return path) to infinity before reducing the matrix.
4. Use Best-First Search, always expanding the node with the lowest lower bound.

3. Approximation Algorithms

Many optimization problems (like TSP, Vertex Cover, Set Cover, Bin Packing) are NP-Hard, meaning there is no known polynomial-time algorithm to solve them exactly. Approximation Algorithms are used to find near-optimal solutions in polynomial time.

Approximation Ratio ():
An algorithm has an approximation ratio of if for any input of size , the cost of the solution produced by the algorithm is within a factor of of the optimal cost :

• For minimization:
• For maximization:

3.1 Vertex-Cover Problem

Problem Statement: Given an undirected graph , find a minimum-size subset of vertices such that every edge in has at least one endpoint in .

2-Approximation Algorithm:

1. Initialize .
2. Initialize .
3. While is not empty:
   • Pick an arbitrary edge .
   • Add both and to .
   • Remove from all edges incident on either or .
4. Return .

Analysis: This guarantees a vertex cover that is at most twice the size of the optimal vertex cover (Approximation ratio ). This is because no two edges picked in step 3 share an endpoint, meaning the optimal solution must pick at least one vertex from every edge we picked. We picked two, so .

3.2 Set-Covering Problem

Problem Statement: Given a universe of elements and a family of subsets of . Find the minimum number of subsets whose union equals .

Greedy Approximation Algorithm:

1. Initialize (the set of picked subsets).
2. Initialize (uncovered elements).
3. While is not empty:
   • Pick the subset that maximizes (the subset that covers the most uncovered elements).
   • Add to .
   • Remove the elements of from .
4. Return .

Analysis: The approximation ratio is . Specifically, it is bounded by , where is the size of the largest set.

3.3 Bin Packing Problems

Problem Statement: Given items with sizes where , pack them into the minimum number of bins, each with a capacity of 1.

Approximation Algorithms:

1. Next Fit (NF):

   • Keep one bin open.
   • If the current item fits in the open bin, put it there.
   • Otherwise, close the bin, open a new one, and put the item in.
   • Approximation Ratio: .

2. First Fit (FF):

   • Keep all used bins open.
   • When considering an item, place it in the first bin that has enough space.
   • If it doesn't fit in any open bin, open a new bin.
   • Approximation Ratio: .

3. First Fit Decreasing (FFD):

   • Sort the items in decreasing order of size.
   • Apply the First Fit algorithm.
   • Approximation Ratio: (Approx 1.22). Sorting heavily reduces the number of wasted gaps in bins.