Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.

A large-scale multichannel sequential detection problem is considered, where an event occurs at some unknown time and affects the distributions of an unknown subset of data streams, possibly at a different time each of them. The goal is to detect this change as quickly as possible, while controlling the false alarm rate. An adaptive CuSum procedure is proposed, whose number of computations at each time instant is linear in the number of streams. Its performance is analyzed in various asymptotic regimes where the number of streams, the unknown number of affected streams, and the unknown delays in the emergence of the change all go to infinity as the false alarm rate goes to zero. The proposed scheme is shown to be asymptotically optimal in sparse and moderately high-dimensional regimes, and to enjoy a superior asymptotic performance to existing procedures in non-sparse or very high-dimensional regimes. Finally, it is compared with existing schemes in the literature in a simulation study.

The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. Weighted requests: In this variant, each demand request is a pair $(x,w)$ where $x$ is the standard location of the demand while $w$ is the corresponding weight of the request. The cost of servicing request $(x,w)$ at facility $F$ is $w\cdot d(x,F)$. For this variant, given $n$ requests, we present an online algorithm attaining a competitive ratio of $\mathcal{O}(\log n)$ in the secretarial model for the weighted requests and show that it is optimal. Congestion: The congestion variant considers the case when there is an additional congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.

In this work, we proposed a novel method, called Local Modified Zernike Moment per unit Mass (LMZMPM), for face recognition, which is invariant to illumination, scaling, noise, in-plane rotation, and translation, along with other orthogonal and inherent properties of the Zernike Moments (ZMs). The proposed LMZMPM is computed for each pixel in a neighborhood of size 3 × 3 , and then considers the complex tuple that contains both the phase and magnitude coefficients of LMZMPM as the extracted features. As it contains both the phase and the magnitude components of the complex feature, it has more information about the image and thus preserves both the edge and structural information. We also propose a hybrid similarity measure, combining the Jaccard Similarity with the L1 distance, and applied to the extracted feature set for classification. The feasibility of the proposed LMZMPM technique on varying illumination has been evaluated on the CMU-PIE and the extended Yale B databases with an average Rank-1 Recognition (R1R) accuracy of 99.8% and 98.66% respectively. To assess the reliability of the method with variations in noise, rotation, scaling, and translation, we evaluate it on the AR database and obtain an average R1R higher than that of recent state-of-the-art methods. The proposed method shows a very high recognition rate on Heterogeneous Face Recognition as well, with 100% on CUFS, and 98.80% on CASIA-HFB.