Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

Highly sensitive optical humidity probe

A highly sensitive optical humidity probe based on reflectance measurements has been developed using Nafion^®-crystal violet (CV) films. This sensor can be used to calibrate relative humidity (RH) in the range 0-0.25% with a detection limit (blank signal + 3σ_b, where σ_b = the standard deviation (S.D.) of the blank signal) of 0.018% RH (∼4.37 ppm) and exhibited low hysteresis. The sensor films were fully reversible in dry nitrogen and reversal times were shown to be dependent on exposure time and % RH. The response to 1% RH was highly reproducible (S.D. = 1.67%, number of samples (n) = 5). Hydrogen chloride gas did not interfere with the response of the sensor to RH but did reduce sensor reversal times. This sensor displayed sufficient sensitivity that it could be used to detect ppm levels of moisture in process gases such as nitrogen and HCl.     

Aggregation modes in sheets formed by protected beta-amino acids and beta-peptides

The crystal structures of four protected beta-amino acid residues, Boc-(S)-beta3-HAla-NHMe (1); Boc-(R)-beta3-HVal-NHMe (2); Boc-(S)-beta3-HPhe-NHMe (3); Boc-(S)-beta3-HPro-OH (6) and two beta-dipeptides, Boc-(R)-beta3-HVal-(R)-beta3-HVal-OMe (4); Boc-(R)-beta3-HVal-(S)-beta3-HVal-OMe (5) have been determined. Gauche conformations about the C(beta)-C(alpha) bonds (theta approximately +/-60 degrees) are observed for the beta3-HPhe residues in and all four beta3-HVal residues in the dipeptides and . Trans conformations (theta is approximately 180 degrees) are observed for beta3-HAla residues in both independent molecules in and for the beta3-HVal and beta3-HPro residues in and , respectively. In the cases of compounds , molecules associate in the crystals via intermolecular backbone hydrogen bonds leading to the formation of sheets. The polar strands formed by beta3-residues aggregate in both parallel (1,3,5) and antiparallel (2,4 fashion. Sheet formation accommodates both the trans and gauche conformations about the C(beta)-C(alpha) bonds.     

Revisiting Best Linear Unbiased Estimation of Location-Scale Parameters Based on Optimally Selected Order Statistics Using Compound Design

Methodology and Computing in Applied Probability - We introduce here the compound optimal design strategy to determine the Best Linear Unbiased Estimates (BLUEs) of location and scale parameters...     

Thermal radiation from photonic crystals: a direct calculation

A classical simulation of equilibrium thermal emissivity from dispersive, lossy photonic crystals is presented. Normal emission results consistent with those assuming Kirchoff's law are obtained; i.e., a photonic crystal does not emit more than what a blackbody does. Significant enhancement, however, can be achieved over the radiation intensity from a uniform slab, indicating the potential usefulness of photonic crystals in incandescent lighting and thermal photovoltaic applications.     

Runs Based on Records: Their Distributional Properties and an Application to Testing for Dispersive Ordering

Here, we study runs associated with record values. After we first discuss the distributions and moments of runs, we develop the asymptotic theory of these runs. Finally, we apply the concept of runs obtained from record values to a hypothesis testing problem.     

A Note on First-Fit Coloring of Interval Graphs

We apply the Column Construction Method (Varadarajan et al., Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms, pp. 562–571, 2004) to a minimal clique cover of an interval graph to obtain a new proof that First-Fit is 8-competitive for online coloring interval graphs. This proof also yields a new discovery that in each minimal clique cover of an interval graph G, there is a clique of size .