Loading [MathJax]/extensions/MathZoom.js
Displaying 181 –
200 of
219
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including...
The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.
The simple plant location problem (SPLP) is considered and
a genetic algorithm is
proposed to solve this problem. By using the developed
algorithm it is possible to solve SPLP
with more than 1000 facility sites and customers.
Computational results are presented and
compared to dual based algorithms.
In this paper a variable neighborhood search (VNS) approach
for the task assignment problem (TAP) is considered. An appropriate neighborhood
scheme along with a shaking operator and local search procedure
are constructed specifically for this problem. The computational results are
presented for the instances from the literature, and compared to optimal
solutions obtained by the CPLEX solver and heuristic solutions generated
by the genetic algorithm. It can be seen that the proposed VNS approach
reaches...
We consider the multiple ellipses detection problem on the basis of a data points set coming from a number of ellipses in the plane not known in advance, whereby an ellipse is viewed as a Mahalanobis circle with center , radius , and some positive definite matrix . A very efficient method for solving this problem is proposed. The method uses a modification of the -means algorithm for Mahalanobis-circle centers. The initial approximation consists of the set of circles whose centers are determined...
Suppose a graph whose edges are partitioned into disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number of categories and present some polynomial algorithm.
The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m⋅log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm...
We study a parameter (σ)
dependent relaxation of the Travelling Salesman Problem on .
The relaxed problem is reduced to the Travelling Salesman Problem
as 0. For increasing σ it is also an
ordered clustering algorithm for a set of points in .
A dual formulation is introduced, which reduces the problem to a
convex optimization, provided the minimizer is in the domain of
convexity of the relaxed functional. It is shown that this last
condition is generically satisfied, provided σ is large
enough.
...
The partial inverse minimum cut problem is to minimally
modify the capacities of a digraph such that
there exists a minimum cut with respect to the new capacities that
contains all arcs of a prespecified set. Orlin showed that the problem is
strongly NP-hard if the amount of
modification is measured by the weighted L1-norm. We prove that the problem
remains hard for the unweighted case and show that the
NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional
bound...
Periodic Vehicle Routing Problem: classification and heuristic for tactical planning.
The Periodic Vehicle Routing Problem (PVRP) consists in assigning customer visits to vehicle routes in some periods of a time horizon so as to satisfy some service level requirements that can take the
form of frequency of visit, constraint on time lag between visits, or pre-defined visit patterns. We present different variants of this problem and propose a classification. Then, we consider a model for tactical...
Currently displaying 181 –
200 of
219