Interval criteria for oscillation of a forced impulsive differential equation with Riemann–Stieltjes integral

In this paper, both El-Sayed type and Kamenev type oscillation criteria for a forced impulsive differential equation with Riemann–Stieltjes integral are established. By using a generalized El-Sayed type function and Kong’s technique in terms of the number of impulse moments on a series of intervals, we not only drop the restriction on the impulse constants $c_k$ and $d_k$ that $d_k\ge c_k$ in the literature, but also extend some existing results to the case of Riemann–Stieltjes integral and improve some results in the case of Riemann integral. Two examples are also considered to illustrate the main results.     

A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem

The Generalized Fermat Problem (in the plane) is: given $n\ge 3$ destination points find the point ${\stackrel{?}{x}}^1$ which minimizes the sum of Euclidean distances from ${\stackrel{?}{x}}^1$ to each of the destination points.The Weiszfeld iterative algorithm for this problem is globally convergent, independent of the initial guess. Also, a test is available, $\stackrel{?}{a}$ priori, to determine when ${\stackrel{?}{x}}^1$ a destination point. This paper generalizes earlier work by the first author by introducing an asymmetric Euclidean distance in which, at each destination, the $x$-component is weighted differently from the $y$-component. A Weiszfeld algorithm is studied to compute ${\stackrel{?}{x}}^1$ and is shown to be a descent method which is globally convergent (except possibly for a denumerable number of starting points). Local convergence properties are characterized. When ${\stackrel{?}{x}}^1$ is not a destination point the iteration matrix at ${\stackrel{?}{x}}^1$ is shown to be convergent and local convergence is always linear. When ${\stackrel{?}{x}}^1$ is a destination point, local convergence can be linear, sub-linear or super-linear, depending upon a computable criterion. A test, which does not require iteration, for ${\stackrel{?}{x}}^1$ to be a destination, is derived. Comparisons are made between the symmetric and asymmetric problems. Numerical examples are given.     

On the approximability of robust spanning tree problems

In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min–max, min–max regret and 2-stage min–max versions of the problem are discussed. The complexity and approximability of all these problems are explored. It is proved that the min–max and min–max regret versions with nonnegative edge costs are hard to approximate within $O\left({log}^{1??}n\right)$ for any $?>0$ unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min–max problem cannot be approximated within $O(logn)$ unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance bound of $O\left({log}^{2}n\right)$ for min–max and 2-stage min–max problems are also proposed.