Sharp upper bounds on the second largest eigenvalues of connected graphs

Let ${\lambda }_2$ be the second largest eigenvalue of a graph. Powers (1988) [4] gave some upper bounds of ${\lambda }_2$ for general graphs and bipartite graphs, respectively. Considering that these bounds are not always attainable for connected graphs, we present sharp upper bounds of ${\lambda }_2$ for connected graphs and connected bipartite graphs in this paper. Moreover, the extremal graphs are completely characterized.     

Optimizing and improving of the C-to-R method for solving complex symmetric linear systems

For complex symmetric linear systems, Axelsson et al. (2014) proposed the C-to-R method. In this paper, by further studying the C-to-R method with $W$ and $T$ being symmetric positive semidefinite, the optimal iteration parameter for the C-to-R method ${\alpha }_{opt}=\frac{\sqrt{2\sqrt{2}}}{2}$ is obtained and the C-to-R method is optimized. Furthermore, based on the optimized C-to-R method, we further propose an optimized preconditioner. Eigenvalue properties of the optimized preconditioned matrix are analyzed, which show that all the eigenvalues of the preconditioned matrix are located in tighter interval. Numerical results are presented, not only confirm the validity of the theoretical analysis, but also demonstrate the feasibility and effectiveness of the proposed optimized C-to-R method.     

Almost sure convergence of the largest and smallest eigenvalues of high-dimensional sample correlation matrices

In this paper, we show that the largest and smallest eigenvalues of a sample correlation matrix stemming from $n$ independent observations of a $p$-dimensional time series with iid components converge almost surely to ${(1+\sqrt{\gamma })}^2$ and ${(1?\sqrt{\gamma })}^2$, respectively, as $n\to \infty$, if $p∕n\to \gamma \in (0,1]$ and the truncated variance of the entry distribution is “almost slowly varying”, a condition we describe via moment properties of self-normalized sums. Moreover, the empirical spectral distributions of these sample correlation matrices converge weakly, with probability $1$, to the Mar?enko–Pastur law, which extends a result in Bai and Zhou (2008). We compare the behavior of the eigenvalues of the sample covariance and sample correlation matrices and argue that the latter seems more robust, in particular in the case of infinite fourth moment. We briefly address some practical issues for the estimation of extreme eigenvalues in a simulation study.In our proofs we use the method of moments combined with a Path-Shortening Algorithm, which efficiently uses the structure of sample correlation matrices, to calculate precise bounds for matrix norms. We believe that this new approach could be of further use in random matrix theory.     

An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times

In the majority of works on online scheduling on multipurpose machines the objective is to minimize the makespan. We, in contrast, consider the objective of minimizing the total completion time. For this purpose, we analyze an online-list scheduling problem of $n$ jobs with unit processing times on a set of two machines working in parallel. Each job belongs to one of two sets of job types. Jobs belonging to the first set can be processed on either of the two machines while jobs belonging to the second set can only be processed on the second machine. We present an online algorithm with a competitive ratio of ${\rho }_{LB}+O\left(\frac{1}{n}\right)$, where ${\rho }_{LB}$ is a lower bound on the competitive ratio of any online algorithm and is equal to $1+{\left(\frac{?\alpha +\sqrt{4{\alpha }^3?{\alpha }^2+2\alpha ?1}}{2{\alpha }^2+1}\right)}^2$ where $\alpha =\frac{1}{3}+\frac{1}{6}{(116?6\sqrt{78})}^{1/3}+\frac{{(58+3\sqrt{78})}^{1/3}}{3{\left(2\right)}^{2/3}}\approx 1.918$. This result implies that our online algorithm is asymptotically optimal.     

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability

This paper is the first successful attempt on differential approximability study for a scheduling problem. Such a study considers the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis shows that the Weighted Shortest Processing Time (WSPT) rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides an approximation with a differential ratio of $\frac{3?\sqrt{5}}{2}\approx 0.38$.     

An improved averaged two-replication procedure with Latin hypercube sampling

The averaged two-replication procedure assesses the quality of a candidate solution to a stochastic program by forming point and confidence interval estimators on its optimality gap. We present an improved averaged two-replication procedure that uses Latin hypercube sampling to form confidence intervals of optimality gap. This new procedure produces tighter and less variable interval widths by reducing the sampling error by $\sqrt{2}$. Despite having tighter intervals, it improves an earlier procedure’s asymptotic coverage probability bound from ${(1?\alpha )}^2$ to $(1?\alpha )$.