Melvin's digital garden

Maximum edge domination problem

Presented by Hirotaka Ono at AAAC 2011

Classical problem of finding minimum edge-dominating set problem. Equivalent to minimum maximal matching problem.

NP-hard, polynomial time 2 approx alg, no poly 7/6 approx

k-Edge Maximum Domination Problem: find k edges that maximizes weight of dominated edges.

Main results:

  • poly 3/4 approx alg,
  • f k is large there is a 1-1/(4e^(a-1)) approx alg
  • No poly algo with 1303/1304 approx

A natural greedy alg achieves is 1-1/e (0.632) approx

  • k-MaxED is a special case of k-Max Coverage Problem

1-1/e approx (new approach)

  • pipage rounding [Ageev1999]
  • a rounding scheme
  • use L(x) for lower bound and F(x) as guideline to round
  • k-MaxED can be reformulated using L(x) and F(x)
  • solve relatex L(x) in polynomial time and round solution using F(x)

3/4 approx

  • pipage rounding with matching constraint
  • any optimal solution forms a matching for smaller k
  • new formulation of L and F

Links to this note