Search results for "Simulation"
showing 10 items of 5095 documents
On Strong Convergence of Halpern’s Method for Quasi-Nonexpansive Mappings in Hilbert Spaces
2016
In this paper, we introduce a Halpern’s type method to approximate common fixed points of a nonexpansive mapping T and a strongly quasi-nonexpansive mappings S, defined in a Hilbert space, such that I − S is demiclosed at 0. The result shows as the same algorithm converges to different points, depending on the assumptions of the coefficients. Moreover, a numerical example of our iterative scheme is given.
An exact method for graph coloring
2006
International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
The Steiner Traveling Salesman Problem and its extensions
2019
Abstract This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.
Simulation is decidable for one-counter nets
1998
We prove that the simulation preorder is decidable for the class of one-counter nets. A one-counter net consists of a finite-state machine operating on a variable (counter) which ranges over the natural numbers. Each transition can increase or decrease the value of the counter. A transition may not be performed if this implies that the value of the counter becomes negative. The class of one-counter nets is computationally equivalent to the class of Petri nets with one unbounded place, and to the class of pushdown automata where the stack alphabet is restricted to one symbol. To our knowledge, this is the first result in the literature which gives a positive answer to the decidability of sim…
On generalized weakly G-contraction mapping in G-metric spaces
2011
In this paper, we establish some common fixed point results for two self-mappings f and g on a generalized metric space X. To prove our results we assume that f is a generalized weakly G-contraction mapping of types A and B with respect to g.
Decidability of bisimulation equivalences for parallel timer processes
1993
In this paper an abstract model of parallel timer processes (PTPs), allowing specification of temporal quantitative constraints on the behaviour of real time systems, is introduced. The parallel timer processes are defined in a dense time domain and are able to model both concurrent (with delay intervals overlapping on the time axis) and infinite behaviour. Both the strong and weak (abstracted from internal actions) bisimulation equivalence problems for PTPs are proved decidable. It is proved also that, if one provides the PTP model additionally with memory cells for moving timer value information along the time axis, the bisimulation equivalence (and even the vertex reachability) problems …
Polyhedral results for a vehicle routing problem
1991
Abstract The Vehicle Routing Problem is a well known, and hard, combinatorial problem, whose polyhedral structure has deserved little attention. In this paper we consider the particular case in which all the demands are equal (since in the general case the associated polytope may be empty). From a known formulation of the problem we obtain the dimension of the corresponding polytope and we study the facetial properties of every inequality in it.
Branch and bound for the cutwidth minimization problem
2013
The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…
Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
2014
The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in bot…
The computational complexity of the relative robust shortest path problem with interval data
2004
Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.