Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Two-timescale Q-learning Algorithms with an Application to Routing in Networks

We propose two variants of the Q-learning algorithm that (both) use two timescales. One of these updates Q-values of all feasible state-action pairs at each instant while the other updates Q-values of states with actions chosen according to the ‘current ’ randomized policy updates. A sketch of convergence of the algorithms is shown. Finally, numerical experiments using the proposed algorithms for routing on different network topologies are presented and performance comparisons with the regular Q-learning algorithm are shown.

Incremental natural-gradient actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic and natural-gradient ideas, and provide their convergence proofs. Actor-critic rein- forcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their com- patibility with function approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further re- duce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal differ- ence learning in the actor and by incorporating natural gradients, and they extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

A Hybrid Energy-insensitive Explicit Guidance Scheme for Long Range Flight Vehicles with Solid Motors

Combining the newly developed nonlinear model predictive static programming technique with null range direction concept, a novel explicit energy-insensitive guidance design method is presented in this paper for long range flight vehicles, which leads to a closed form solution of the necessary guidance command update. Owing to the closed form nature, it does not lead to computational difficulties and the proposed optimal guidance algorithm can be implemented online. The guidance law is verified in a solid motor propelled long range flight vehicle, for which coming up with an effective guidance law is more difficult as compared to a liquid engine propelled vehicle (mainly because of the absence of thrust cutoff facility). Assuming the starting point of the second stage to be a deterministic point beyond the atmosphere, the scheme guides the vehicle properly so that it completes the mission within a tight error bound. The simulation results demonstrate its ability to intercept the target, even with an uncertainty of greater than 10% in burnout time.

Sliding mode control-based algorithms for consensus in connected swarms

In this article, finite-time consensus algorithms for a swarm of self-propelling agents based on sliding mode control and graph algebraic theories are presented. Algorithms are developed for swarms that can be described by balanced graphs and that are comprised of agents with dynamics of the same order. Agents with first and higher order dynamics are considered. For consensus, the agents' inputs are chosen to enforce sliding mode on surfaces dependent on the graph Laplacian matrix. The algorithms allow for the tuning of the time taken by the swarm to reach a consensus as well as the consensus value. As an example, the case when a swarm of first-order agents is in cyclic pursuit is considered.

Re-entrant behavior in dynamics of binary mixtures of soft hybrid nanocolloids and homopolymers

We present results of measurements of temperature and wavevector dependent dynamics in binary mixtures of soft polymer grafted nanoparticles and linear homopolymers. We find evidence of melting of the dynamically arrested state of the soft nanocolloids with addition of linear polymers followed by a re-entrant slowing down of the dynamics with further increase in polymer density, depending on the size ratio, delta, of the polymers and the nanocolloids. For higher delta the re-entrant behavior is not observed, even for the highest added polymer density, explored here. Possible explanation of the observed dynamics in terms of the presence of a double - glass phase is provided. (C) 2011 American Institute of Physics. [doi:10.1063/1.3644930]

Stochastic Algorithms for Discrete Parameter Simulation Optimization

We present two efficient discrete parameter simulation optimization (DPSO) algorithms for the long-run average cost objective. One of these algorithms uses the smoothed functional approximation (SFA) procedure, while the other is based on simultaneous perturbation stochastic approximation (SPSA). The use of SFA for DPSO had not been proposed previously in the literature. Further, both algorithms adopt an interesting technique of random projections that we present here for the first time. We give a proof of convergence of our algorithms. Next, we present detailed numerical experiments on a problem of admission control with dependent service times. We consider two different settings involving parameter sets that have moderate and large sizes, respectively. On the first setting, we also show performance comparisons with the well-studied optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm. Note to Practitioners-Even though SPSA and SFA have been devised in the literature for continuous optimization problems, our results indicate that they can be powerful techniques even when they are adapted to discrete optimization settings. OCBA is widely recognized as one of the most powerful methods for discrete optimization when the parameter sets are of small or moderate size. On a setting involving a parameter set of size 100, we observe that when the computing budget is small, both SPSA and OCBA show similar performance and are better in comparison to SFA, however, as the computing budget is increased, SPSA and SFA show better performance than OCBA. Both our algorithms also show good performance when the parameter set has a size of 10(8). SFA is seen to show the best overall performance. Unlike most other DPSO algorithms in the literature, an advantage with our algorithms is that they are easily implementable regardless of the size of the parameter sets and show good performance in both scenarios.

A hybrid pre-whitening technique for detection of additive spread spectrum watermarks in audio signals

Pre-whitening techniques are employed in blind correlation detection of additive spread spectrum watermarks in audio signals to reduce the host signal interference. A direct deterministic whitening (DDW) scheme is derived in this paper from the frequency domain analysis of the time domain correlation process. Our experimental studies reveal that, the Savitzky-Golay Whitening (SGW), which is otherwise inferior to DDW technique, performs better when the audio signal is predominantly lowpass. The novelty of this paper lies in exploiting the complementary nature to the two whitening techniques to obtain a hybrid whitening (HbW) scheme. In the hybrid scheme the DDW and SGW techniques are selectively applied, based on short time spectral characteristics of the audio signal. The hybrid scheme extends the reliability of watermark detection to a wider range of audio signals.

Quantum Algorithms with Fixed Points: The Case of Database Search

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes

We study a class of symmetric discontinuous Galerkin methods on graded meshes. Optimal order error estimates are derived in both the energy norm and the L 2 norm, and we establish the uniform convergence of V-cycle, F-cycle and W-cycle multigrid algorithms for the resulting discrete problems. Numerical results that confirm the theoretical results are also presented.