Approximation Algorithms Flashcards
What is an approximation algorithm?
An algorithm that finds near-optimal solutions to problems in polynomial time, with a guarantee on how close the solution is to the optimal.
What are the four general techniques for designing approximation algorithms?
- Greedy algorithms, 2. Pricing methods, 3. Linear programming and rounding, 4. Dynamic programming on rounded inputs.
What is the primary goal of an approximation algorithm?
To provide solutions close to optimal for problems where finding an exact solution is computationally infeasible.
Why are approximation guarantees important in these algorithms?
They ensure that the solution is provably close to the optimal, even though the exact solution is hard to compute.
What is the Load Balancing Problem?
Assigning jobs to machines to minimize the maximum load (makespan) across all machines.
Describe the greedy algorithm for the Load Balancing Problem.
Assign each job to the machine with the smallest current load.
What is the approximation ratio for the basic greedy load balancing algorithm?
The makespan is at most 2 times the optimal makespan (T ≤ 2T*).
How can the greedy load balancing algorithm be improved?
By sorting jobs in decreasing order of processing times before assignment, reducing the approximation factor to 1.5.
What is the Center Selection Problem?
Selecting k centers from a set of sites to minimize the maximum distance (covering radius) between a site and its nearest center.
What guarantees does the greedy algorithm provide for the Center Selection Problem?
It finds a solution with a covering radius at most twice the optimal.
What is the key flaw in a naive greedy approach for Center Selection?
It may select suboptimal centers and produce arbitrarily bad solutions due to shortsighted decisions.
What is the Set Cover Problem?
Finding the smallest collection of subsets that cover a universal set of elements.
Describe the greedy approach to solving the Set Cover Problem.
Iteratively select the subset with the lowest cost per uncovered element until all elements are covered.
What is the approximation factor for the greedy Set Cover algorithm?
H(d), where d is the size of the largest subset (H(d) is the d-th harmonic number).
Why is the greedy Set Cover algorithm not optimal?
The approximation guarantee is logarithmic in the number of elements, which can be large.
What is the Vertex Cover Problem?
Finding the smallest subset of vertices in a graph such that every edge has at least one endpoint in the subset.
How can the Vertex Cover Problem be reduced to Set Cover?
Each vertex represents a set of edges it covers; finding a minimum vertex cover is equivalent to finding a minimum set cover.
What is the approximation ratio of the pricing method for Vertex Cover?
The algorithm guarantees a solution within 2 times the optimal weight.
What is the Disjoint Paths Problem?
Finding the maximum number of edge-disjoint paths connecting designated source-sink pairs in a graph.
What is the approximation guarantee for the greedy algorithm for the Disjoint Paths Problem?
An O(√m)-approximation, where m is the number of edges.
How does increasing edge capacity (c > 1) affect Disjoint Paths approximations?
With c = 2 and β = m^(1/3), the approximation improves to O(m^(1/3)).
What is Linear Programming (LP)?
An optimization technique where a linear objective function is maximized or minimized subject to linear equality or inequality constraints.
How is Vertex Cover formulated as an integer program (IP)?
Minimize the sum of vertex weights subject to constraints ensuring each edge has at least one endpoint in the vertex cover.
Why is Integer Programming (IP) hard for Vertex Cover?
Adding the constraint that variables are integers makes the problem NP-complete.
What is the key difference between LP and IP?
LP allows real-valued solutions, whereas IP restricts solutions to integers.
What is the advantage of using LP relaxation for Vertex Cover?
It provides a lower bound on the optimal solution and a framework to find an approximate solution.
How is rounding used to approximate Vertex Cover using LP?
Nodes with fractional values ≥ 0.5 in the LP solution are included in the vertex cover.
What is the approximation ratio for the LP-based rounding algorithm for Vertex Cover?
2, as it guarantees a solution at most twice the optimal weight.
Why is LP rounding a powerful technique?
It bridges the gap between real-valued solutions and integer constraints, providing efficient approximations for NP-hard problems.
What is the significance of H(d) in Set Cover approximations?
H(d) represents the harmonic number used in the approximation factor, reflecting the difficulty of covering large sets.
Explain how binary search is used in the Center Selection Problem.
Binary search guesses the optimal radius, refining the guess until it finds a radius close to the actual optimal.
Why is knowing the optimal radius useful in the Center Selection Problem?
It helps identify whether a given set of k centers can achieve the desired covering radius.
Why is the pricing method effective for Vertex Cover?
It ensures fairness by assigning costs to edges that approximately cover the weights of vertices.
