Search results for "Combinatorics"

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.

Cotas inferiores para el QAP-Arbol

1985

The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.

Large deviations results for subexponential tails, with applications to insurance risk

1996

AbstractConsider a random walk or Lévy process {St} and let τ(u) = inf {t⩾0 : St > u}, P(u)(·) = P(· | τ(u) < ∞). Assuming that the upwards jumps are heavy-tailed, say subexponential (e.g. Pareto, Weibull or lognormal), the asymptotic form of the P(u)-distribution of the process {St} up to time τ(u) is described as u → ∞. Essentially, the results confirm the folklore that level crossing occurs as result of one big jump. Particular sharp conclusions are obtained for downwards skip-free processes like the classical compound Poisson insurance risk process where the formulation is in terms of total variation convergence. The ideas of the proof involve excursions and path decompositions for Mark…

Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?

2011

The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix at step $n+1$ \[ S_n = Cov(X_1,...,X_n) + \epsilon I, \] that is, the sample covariance matrix of the history of the chain plus a (small) constant $\epsilon>0$ multiple of the identity matrix $I$. The lower bound on the eigenvalues of $S_n$ induced by the factor $\epsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\epsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away …

2021

Abstract We prove the existence of a smoothing for a toroidal crossing space under mild assumptions. By linking log structures with infinitesimal deformations, the result receives a very compact form for normal crossing spaces. The main approach is to study log structures that are incoherent on a subspace of codimension 2 and prove a Hodge–de Rham degeneration theorem for such log spaces that also settles a conjecture by Danilov. We show that the homotopy equivalence between Maurer–Cartan solutions and deformations combined with Batalin–Vilkovisky theory can be used to obtain smoothings. The construction of new Calabi–Yau and Fano manifolds as well as Frobenius manifold structures on moduli…

Explicit, identical maximum likelihood estimates for some cyclic Gaussian and cyclic Ising models

2017

Cyclic models are a subclass of graphical Markov models with simple, undirected probability graphs that are chordless cycles. In general, all currently known distributions require iterative procedures to obtain maximum likelihood estimates in such cyclic models. For exponential families, the relevant conditional independence constraint for a variable pair is given all remaining variables, and it is captured by vanishing canonical parameters involving this pair. For Gaussian models, the canonical parameter is a concentration, that is, an off-diagonal element in the inverse covariance matrix, while for Ising models, it is a conditional log-linear, two-factor interaction. We give conditions un…

PROBABILISTIC QUANTIFICATION OF HAZARDS: A METHODOLOGY USING SMALL ENSEMBLES OF PHYSICS-BASED SIMULATIONS AND STATISTICAL SURROGATES

2015

This paper presents a novel approach to assessing the hazard threat to a locale due to a large volcanic avalanche. The methodology combines: (i) mathematical modeling of volcanic mass flows; (ii) field data of avalanche frequency, volume, and runout; (iii) large-scale numerical simulations of flow events; (iv) use of statistical methods to minimize computational costs, and to capture unlikely events; (v) calculation of the probability of a catastrophic flow event over the next T years at a location of interest; and (vi) innovative computational methodology to implement these methods. This unified presentation collects elements that have been separately developed, and incorporates new contri…