Approximation Algorithms

Question 1

What is an approximation algorithm?

Answer 1

An algorithm that finds near-optimal solutions to problems in polynomial time, with a guarantee on how close the solution is to the optimal.

Question 2

What are the four general techniques for designing approximation algorithms?

Answer 2

1. Greedy algorithms, 2. Pricing methods, 3. Linear programming and rounding, 4. Dynamic programming on rounded inputs.

Question 3

What is the primary goal of an approximation algorithm?

Answer 3

To provide solutions close to optimal for problems where finding an exact solution is computationally infeasible.

Question 4

Why are approximation guarantees important in these algorithms?

Answer 4

They ensure that the solution is provably close to the optimal, even though the exact solution is hard to compute.

Question 5

What is the Load Balancing Problem?

Answer 5

Assigning jobs to machines to minimize the maximum load (makespan) across all machines.

Question 6

Describe the greedy algorithm for the Load Balancing Problem.

Answer 6

Assign each job to the machine with the smallest current load.

Question 7

What is the approximation ratio for the basic greedy load balancing algorithm?

Answer 7

The makespan is at most 2 times the optimal makespan (T ≤ 2T*).

Question 8

How can the greedy load balancing algorithm be improved?

Answer 8

By sorting jobs in decreasing order of processing times before assignment, reducing the approximation factor to 1.5.

Question 9

What is the Center Selection Problem?

Answer 9

Selecting k centers from a set of sites to minimize the maximum distance (covering radius) between a site and its nearest center.

Question 10

What guarantees does the greedy algorithm provide for the Center Selection Problem?

Answer 10

It finds a solution with a covering radius at most twice the optimal.

Question 11

What is the key flaw in a naive greedy approach for Center Selection?

Answer 11

It may select suboptimal centers and produce arbitrarily bad solutions due to shortsighted decisions.

Question 12

What is the Set Cover Problem?

Answer 12

Finding the smallest collection of subsets that cover a universal set of elements.

Question 13

Describe the greedy approach to solving the Set Cover Problem.

Answer 13

Iteratively select the subset with the lowest cost per uncovered element until all elements are covered.

Question 14

What is the approximation factor for the greedy Set Cover algorithm?

Answer 14

H(d), where d is the size of the largest subset (H(d) is the d-th harmonic number).

Question 15

Why is the greedy Set Cover algorithm not optimal?

Answer 15

The approximation guarantee is logarithmic in the number of elements, which can be large.

Question 16

What is the Vertex Cover Problem?

Answer 16

Finding the smallest subset of vertices in a graph such that every edge has at least one endpoint in the subset.

Question 17

How can the Vertex Cover Problem be reduced to Set Cover?

Answer 17

Each vertex represents a set of edges it covers; finding a minimum vertex cover is equivalent to finding a minimum set cover.

Question 18

What is the approximation ratio of the pricing method for Vertex Cover?

Answer 18

The algorithm guarantees a solution within 2 times the optimal weight.

Question 19

What is the Disjoint Paths Problem?

Answer 19

Finding the maximum number of edge-disjoint paths connecting designated source-sink pairs in a graph.

Question 20

What is the approximation guarantee for the greedy algorithm for the Disjoint Paths Problem?

Answer 20

An O(√m)-approximation, where m is the number of edges.

Question 21

How does increasing edge capacity (c > 1) affect Disjoint Paths approximations?

Answer 21

With c = 2 and β = m^(1/3), the approximation improves to O(m^(1/3)).

Question 22

What is Linear Programming (LP)?

Answer 22

An optimization technique where a linear objective function is maximized or minimized subject to linear equality or inequality constraints.

Question 23

How is Vertex Cover formulated as an integer program (IP)?

Answer 23

Minimize the sum of vertex weights subject to constraints ensuring each edge has at least one endpoint in the vertex cover.

Question 24

Why is Integer Programming (IP) hard for Vertex Cover?

Answer 24

Adding the constraint that variables are integers makes the problem NP-complete.

Question 25

What is the key difference between LP and IP?

Answer 25

LP allows real-valued solutions, whereas IP restricts solutions to integers.

Question 26

What is the advantage of using LP relaxation for Vertex Cover?

Answer 26

It provides a lower bound on the optimal solution and a framework to find an approximate solution.

Question 27

How is rounding used to approximate Vertex Cover using LP?

Answer 27

Nodes with fractional values ≥ 0.5 in the LP solution are included in the vertex cover.

Question 28

What is the approximation ratio for the LP-based rounding algorithm for Vertex Cover?

Answer 28

2, as it guarantees a solution at most twice the optimal weight.

Question 29

Why is LP rounding a powerful technique?

Answer 29

It bridges the gap between real-valued solutions and integer constraints, providing efficient approximations for NP-hard problems.

Question 30

What is the significance of H(d) in Set Cover approximations?

Answer 30

H(d) represents the harmonic number used in the approximation factor, reflecting the difficulty of covering large sets.

Question 31

Explain how binary search is used in the Center Selection Problem.

Answer 31

Binary search guesses the optimal radius, refining the guess until it finds a radius close to the actual optimal.

Question 32

Why is knowing the optimal radius useful in the Center Selection Problem?

Answer 32

It helps identify whether a given set of k centers can achieve the desired covering radius.

Question 33

Why is the pricing method effective for Vertex Cover?

Answer 33

It ensures fairness by assigning costs to edges that approximately cover the weights of vertices.