Approximation algorithm

Suppose a growing nearest-neighbor service cannot search its entire dataset before a request times out. One option is to search random shards in parallel and return the best result found. The answer may not be the true nearest neighbor, but it can arrive within the available time. An approximation algorithm makes this kind of trade-off: it seeks a useful solution without requiring the exact optimum. section 11.3.1

Approximate does not always mean unbounded guesswork. An algorithm with approximation factor a returns a solution valued at most a times the optimum, when that guarantee applies. For minimum vertex cover, polynomial-time algorithms have a factor on the order of 2. Exact polynomial-time solutions exist for particular graph categories, including bipartite graphs and trees; for other cases, accepting a non-optimal answer avoids the exponential-time alternative. section 18.3

Choose an approach by identifying what makes the exact answer difficult:

• For a high-dimensional point cluster, the exact smallest enclosing sphere has an algorithm exponential in the number of dimensions. Start from the cluster’s center of mass, repeatedly move toward its farthest point, and shorten the maximum move after each iteration. This approximates a tighter covering sphere than the one fixed at the center of mass. section 10.5.2
• For graph embedding, try several valid random placements of vertices and retain the one with the fewest edge intersections. More trials give the search more chances to find a good placement, but this heuristic supplies no stated approximation-factor guarantee. section 16.1.1

function randomEmbedding(graph, W, H, runs)                #1
  kBest ← inf                                              #2
  for i in {1..runs} do                                    #3
    embedding ← []                                         #4
    for j in {0..|graph.vertices|-1} do                    #5
      x ← random(0, W)                                     #6
      y ← random(0, H)
      embedding[j] ← (x,y)                                 #7
    if not validateEmbedding(embedding, graph) then        #8
      i--
    else
      k ← edgeIntersections(graph, embedding)              #9
      if k < kBest then                                    #10
        kBest ← k
        embeddingBest ← embedding
  return embeddingBest                                     #11

The random-embedding listing makes the heuristic concrete: generate positions, reject invalid placements, count crossings, and keep the best valid candidate. section 16.1.1

Assess both solution quality and work required. The embedding heuristic checks vertex pairs and vertex–edge combinations to validate a candidate, then compares pairs of edges to count intersections. Repeating these checks costs time; rejecting invalid placements can require additional attempts. Where a guaranteed quality bound matters, distinguish a proven approximation factor from simply returning the best candidate sampled so far. section 16.1.1 section 18.3