Search results for " Combinatoric"
showing 10 items of 299 documents
Suffix array and Lyndon factorization of a text
2014
Abstract The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we prop…
Radio k-Labelings for Cartesian Products of Graphs
2005
International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…
A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
2021
Abstract The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques …
EMERGENCE OF TRAVELLING WAVES IN SMOOTH NERVE FIBRES
2008
International audience; An approximate analytical solution characterizing initial condi- tions leading to action potential ¯ring in smooth nerve ¯bres is determined, using the bistable equation. In the ¯rst place, we present a non-trivial sta- tionary solution wave. Then, we extract the main features of this solution to obtain a frontier condition between the initiation of the travelling waves and a decay to the resting state. This frontier corresponds to a separatrix in the projected dynamics diagram depending on the width and the amplitude of the stationary wave.
A multi-local optimization algorithm
1998
The development of efficient algorithms that provide all the local minima of a function is crucial to solve certain subproblems in many optimization methods. A “multi-local” optimization procedure using inexact line searches is presented, and numerical experiments are also reported. An application of the method to a semi-infinite programming procedure is included.
The Serial Property and Restricted Balanced Contributions in discrete cost sharing problems
2006
We show that the Serial Poperty and Restricted Balanced Contributions characterize the subsidy-free serial cost sharing method (Moulin (1995)) in discrete cost allocation problems.
Hores: A timetabling system for Spanish secondary schools
1995
Constructing a timetable is a difficult problem faced by every school every year. A feasible solution has to satisfy many different requirements and constraints. A good solution has to provide compact timetables for classes and teachers. In order to help the schools, we have developed HORES, a robust and flexible timetabling system suited to the needs of Spanish secondary schools. HORES runs on a PC and is fast and user-friendly. It may handle virtually every condition required by the schools and obtains good quality solutions in very short computing times. It also allows the user to modify interactively the solutions. HORES is now being used by schools with satisfactory results.
Comparacion numerica de algoritmos para calcular distribuciones estacionarias de cadenas de Markov finitas
1992
En este trabajo se estudia la eficiencia de un conjunto de algoritmos, exactos e iterativos, para el problema de obtener la distribucion estacionaria de una cadena de Markov homogenea, irreducible y finita. Se presentan los resultados computacionales obtenidos al resolver problemas de diferentes tipos y tamanos, aleatoriamente generados, asi como el tratamiento estadistico realizado sobre los mismos. Se ha comparado la estabilidad de estos algoritmos frente a la perdida de irreducibilidad y la existencia de estados transitorios mediante su aplicacion a 26 problemas test. El trabajo concluye con una discusion del comportamiento de los diversos algoritmos.
Estudio bayesiano de los periodos de ocupacion y desocupacion en una cola M/M/1/∞/FIFO en equilibrio
1986
En este articulo, para un modelo de colas M/M/1/8/FIFO en equilibrio, se obtiene la distribucion predictiva del tiempo de duracion de un periodo de ocupacion, y de desocupacion de la cola, asi como la distribucion predictiva final del numero de personas atendidas en un periodo de ocupacion, y la probabilidad de que este sea finito. Finalmente, dichos resultados se aplican en una linea de espera concreta.
Searching for a strong double tracing in a graph
1998
Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.