**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**5

# Search results for: approximation algorithms

##### 5 A Mixed Integer Linear Programming Model for Flexible Job Shop Scheduling Problem

**Authors:**
Mohsen Ziaee

**Abstract:**

**Keywords:**
Scheduling,
flexible job shop,
makespan,
mixed integer linear programming.

##### 4 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:**
Weighted vertex cover,
vertex support,
approximation algorithms,
NP-complete problem.

##### 3 Optimization of Unweighted Minimum Vertex Cover

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

**Abstract:**

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

##### 2 Block Sorting: A New Characterization and a New Heuristic

**Authors:**
Swapnoneel Roy,
Ashok Kumar Thakur,
Minhazur Rahman

**Abstract:**

**Keywords:**
Block Sorting,
Optical Character Recognition,
Genome Rearrangements,
Sorting Primitives,
ApproximationAlgorithms

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

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

**Abstract:**

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