All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 15 of 15

Showing per page

The behavior of a Markov network with respect to an absorbing class: the target algorithm

Giacomo Aletti (2009)

RAIRO - Operations Research

In this paper, we face a generalization of the problem of finding the distribution of how long it takes to reach a “target” set T of states in Markov chain. The graph problems of finding the number of paths that go from a state to a target set and of finding the n-length path connections are shown to belong to this generalization. This paper explores how the state space of the Markov chain can be reduced by collapsing together those states that behave in the same way for the purposes of calculating...

The Friendship Theorem

Karol Pąk (2012)

Formalized Mathematics

In this article we prove the friendship theorem according to the article [1], which states that if a group of people has the property that any pair of persons have exactly one common friend, then there is a universal friend, i.e. a person who is a friend of every other person in the group

The inverse maximum flow problem considering l∞ norm

Adrian Deaconu (2008)

RAIRO - Operations Research

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...

The Orderly Colored Longest Path Problem – a survey of applications and new algorithms

Marta Szachniuk, Maria Cristina De Cola, Giovanni Felici, Jacek Blazewicz (2014)

RAIRO - Operations Research - Recherche Opérationnelle

A concept of an Orderly Colored Longest Path (OCLP) refers to the problem of finding the longest path in a graph whose edges are colored with a given number of colors, under the constraint that the path follows a predefined order of colors. The problem has not been widely studied in the previous literature, especially for more than two colors in the color arrangement sequence. The recent and relevant application of OCLP is related to the interpretation of Nuclear Magnetic Resonance experiments for...

The traveling salesman problem and harmonic analysis.

Peter W. Jones (1991)

Publicacions Matemàtiques

In this paper we propose to discuss some relationships between the classical Traveling Salesman Problem (TSP), Litlewood-Paley theory, and harmonic measure. This circle of ideas is also closely related to the theory of Cauchy integrals on Lipschitz graphs, and this aspect is discussed more fully in the paper of David and Semmes [2] in this proceedings. The main differences between the subjects in [2] and this paper are that the results here are valid for one dimensional sets, whereas [2] treats...

Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem

Hervé Kerivin, Mathieu Lacroix, Alain Quilliot, Hélène Toussaint (2011)

RAIRO - Operations Research

In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the...

Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem

Hervé Kerivin, Mathieu Lacroix, Alain Quilliot, Hélène Toussaint (2011)

RAIRO - Operations Research

In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the...

Currently displaying 1 – 15 of 15

Page 1