Abstract: This research presents the first constant approximation
algorithm to the p-median network design problem with multiple
cable types. This problem was addressed with a single cable type and
there is a bifactor approximation algorithm for the problem. To the
best of our knowledge, the algorithm proposed in this paper is the first
constant approximation algorithm for the p-median network design
with multiple cable types. The addressed problem is a combination of
two well studied problems which are p-median problem and network
design problem. The introduced algorithm is a random sampling
approximation algorithm of constant factor which is conceived by
using some random sampling techniques form the literature. It is
based on a redistribution Lemma from the literature and a steiner tree
problem as a subproblem. This algorithm is simple, and it relies on the
notions of random sampling and probability. The proposed approach
gives an approximation solution with one constant ratio without
violating any of the constraints, in contrast to the one proposed in the
literature. This paper provides a (21 + 2)-approximation algorithm
for the p-median network design problem with multiple cable types
using random sampling techniques.
Abstract: The median problem is significantly applied to derive
the most reasonable rearrangement phylogenetic tree for many
species. More specifically, the problem is concerned with finding
a permutation that minimizes the sum of distances between itself
and a set of three signed permutations. Genomes with equal number
of genes but different order can be represented as permutations.
In this paper, an algorithm, namely BeamGA median, is proposed
that combines a heuristic search approach (local beam) as an
initialization step to generate a number of solutions, and then a
Genetic Algorithm (GA) is applied in order to refine the solutions,
aiming to achieve a better median with the smallest possible reversal
distance from the three original permutations. In this approach,
any genome rearrangement distance can be applied. In this paper,
we use the reversal distance. To the best of our knowledge, the
proposed approach was not applied before for solving the median
problem. Our approach considers true biological evolution scenario
by applying the concept of common intervals during the GA
optimization process. This allows us to imitate a true biological
behavior and enhance genetic approach time convergence. We were
able to handle permutations with a large number of genes, within
an acceptable time performance and with same or better accuracy as
compared to existing algorithms.