**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**4

# approximation algorithms Related Publications

##### 4 Constant Factor Approximation Algorithm for p-Median Network Design Problem with Multiple Cable Types

**Authors:**
Chaghoub Soraya,
Zhang Xiaoyan

**Abstract:**

**Keywords:**
Network Design,
approximation algorithms,
buy-at-bulk,
p-median,
combinatorial
optimization

##### 3 An Effective Algorithm for Minimum Weighted Vertex Cover Problem

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

**Keywords:**
approximation algorithms,
Weighted vertex cover,
vertex support,
NP-complete problem

##### 2 Optimization of Unweighted Minimum Vertex Cover

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

**Keywords:**
approximation algorithms,
vertex support,
vertex cover,
NP - complete problem

##### 1 Approximation Algorithm for the Shortest Approximate Common Superstring Problem

**Authors:**
A.S. Rebaï,
M. Elloumi

**Abstract:**

**Keywords:**
approximation algorithms,
Shortest approximate common superstring,
strings overlaps,
complexities