The edge dominating set problem is one of the fundamental covering problems in the field of combinatorial optimization. In this paper, we consider the b-edge dominating set problem, a generalized version of the edge dominating set problem. In this version, we are given a simple undirected graph G = (V, E) and a demand vector b ∈ Z_+~E. A set F of edges in G is called a b-edge dominating set if each edge e ∈ E is adjacent to at least b(e) edges in F, where we allow F to contain multiple copies of edges in E. Given a cost vector w ∈ Q_+~E, the problem asks to find a minimum cost of a b-edge dominating set. We first show that there is a 8/3-approximation algorithm for this problem. We then consider approximation algorithms for other related problems.
展开▼
