Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results

We present anO(p · n) algorithm for the problem of finding disjoint simple paths of minimum total length betweenp given pairs of terminals on oriented partial 2-trees withn nodes and positive or negative arc lengths. The algorithm is inO(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the casep=2.We gratefully acknowledge the referee's many helpful suggestions to improve the presentation of this paper.     

On the average length of lexicographic paths

A bound is given for the average length of a lexicographic path, a definition that is motivated by degeneracies encountered when using the randomized simplex method.     

About the influence of friction and polydispersity on the jamming behavior of bead assemblies

We study the jamming of bead assemblies placed in a cylindrical container whose bottom is pierced with a circular hole. Their jamming behavior is quantified here by the median jamming diameter, that is the diameter of the hole for which the jamming probability is 0.5. Median jamming diameters of monodisperse assemblies are obtained numerically using the Distinct Element Method and experimentally with steel beads. We obtain good agreement between numerical and experimental results. The influence of friction is then investigated. In particular, the formation of concentric bead rings is observed for low frictions. We identify this phenomenon as a boundary effect and study its influence on jamming. Relying on measures obtained from simulation runs, the median jamming diameter of bidisperse bead assemblies is finally found to depend only on the volume-average diameter of their constituting beads. We formulate this as a tentative law and validate it using bidisperse assemblies of steel beads.     

Tracking elementary particles near their primary vertex: A combinatorial approach

Colliding beams experiments in High Energy Physics rely on solid state detectors to track the flight paths of charged elementary particles near their primary point of interaction. Reconstructing tracks in this region requires, per collision, a partitioning of up to 10³ highly correlated observations into an unknown number of tracks. We report on the successful implementation of a combinatorial track finding algorithm to solve this pattern recognition problem in the context of the ALEPH experiment at CERN. Central to the implementation is a 5-dimensional axial assignment model (AP5) encompassing noise and inefficiencies of the detector, whose weights of assignments are obtained by means of an extended Kalman filter. A preprocessing step, involving the clustering and geometric partitioning of the observations, ensures reasonable bounds on the size of the problems, which are solved using a branch & bound algorithm with LP relaxation. Convergence is reached within one second of CPU time on a RISC workstation in average.     

Zusatz zur korrektur

Zusatz zur korrektur