The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Given a graph G = (V,E) and a “cost function” (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition.
We provide a polynomial time dynamic program for the case where G is an interval graph and f belongs to a subclass of submodular set functions, which we call “value-polymatroidal”.
This provides a common solution for various generalizations of the...
The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate...
In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O()-time algorithm is given, where is a number of restriction...
In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of...
Comparing q-ary relations on a set of elementary objects is one of the most fundamental problems of
classification and combinatorial data analysis. In this paper the specific comparison task that involves classification
tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is
defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to
tree comparison are discussed in the context...
Comparing q-ary relations on a set of
elementary objects is one of the most fundamental problems of
classification and combinatorial data analysis. In this paper the
specific comparison task that involves
classification tree structures (binary or not) is considered in this
context. Two mathematical representations
are proposed. One is defined in terms of a weighted binary relation;
the second uses a 4-ary relation.
The most classical approaches to tree comparison are discussed in the
context...
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
For a given partial solution,
the partial inverse problem is to modify the coefficients
such that there is a full solution containing the partial solution,
while the full solution becomes optimal under new coefficients, and
the total modification is minimum.
In this paper, we show that the partial inverse
assignment problem and the partial inverse minimum cut problem are NP-hard if
there are bound constraints on the changes of coefficients.
Ce travail porte sur l'optimisation des lignes
d'usinage pour la grande série. Une telle ligne comporte plusieurs
postes de travail, chacun étant équipé avec boîtiers multibroches. Un
boîtier multibroche exécute plusieurs opérations en parallèle.
Lors de la conception en avant-projet,
il est nécessaire d'affecter toutes les opérations à des boîtiers et
des postes de travail de sorte à minimiser le nombre de postes et de
boîtiers utilisés. Pour ce nouveau problème d'équilibrage des lignes
de production,...
In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.
In this paper, we study the problem of computing a minimum cost
Steiner tree subject to a weight constraint in a Halin graph where
each edge has a nonnegative integer cost and a nonnegative integer
weight. We prove the NP-hardness of this problem and present a
fully polynomial time approximation scheme for this NP-hard problem.
We consider continuous reformulations of the euclidean travelling salesperson problem (TSP), based on certain clustering problem formulations. These reformulations allow us to apply a generalisation with perturbations of the Weiszfeld algorithm in an attempt to find local approximate solutions to the euclidean TSP.
We consider continuous reformulations of the Euclidean travelling
salesperson problem (TSP), based on certain clustering problem
formulations. These reformulations allow us to apply a generalisation
with perturbations of the Weiszfeld algorithm in an attempt to
find local approximate solutions to the Euclidean TSP.
Traditional traffic control systems based on traffic light have achieved a great success in reducing the average delay of vehicles or in improving the traffic capacity. The main idea of these systems is based on the optimization of the cycle time, the phase sequence, and the phase duration. The right-of-ways are assigned to vehicles of one or several movements for a specific time. With the emergence of cooperative driving, an innovative traffic control concept, Autonomous Intersection Management...
Currently displaying 1 –
20 of
22