Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

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

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.

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.

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.

Gibbs free energies of formation of ZnAl2O4 and ZnCr2O4

The standard free energies of formation of zinc aluminate and chromite were determined by measuring the oxygen potential over a solid CuZn alloy, containing 10 at.−% Zn, in equilibrium with ZnO, ZnAl2O4+Al2O3(χ) and ZnCr2O4+Cr2O3, in the temperature range 700–900°C. The oxygen potential was monitored by means of a solid oxide galvanic cell in which a Y2O3 ThO2 pellet was sandwiched between a CaOZrO2 crucible and tube. The temperature dependence of the free energies of formation of the interoxidic compounds can be represented by the equations, The heat of formation of the spinels calculated from the measurements by the “Second Law method” is found to be in good agreement with calorimetrically determined values. Using an empirical correlation for the entropy of formation of cubic spinel phases from oxides with rock-salt and corundum structures and the measured high temperature cation distribution in ZnAl2O4, the entropy of transformation of ZnO from wurtzite to rock-salt structure is evaluated.

Potentiometric determination of the Gibbs free energy of formation of cadmium and magnesium chromites

The standard Gibbs free energy of formation of magnesium and cadmiumchromites have been determined by potentiometric measurements on reversiblesolid-state electrochemical cells [dformula (Au-5%Cd, , Au-5%Cd; Pt, + , CaO-ZrO[sub 2], + ,Pt; CdO, , CdCr[sub 2]O[sub 4] + Cr[sub 2]O[sub 3])] in the temperature range 500°–730°C, and [dformula Pt, Cr + Cr[sub 2]O[sub 3]/Y[sub 2]O[sub 3]-ThO[sub 2]/Cr + MgCr[sub 2]O[sub 4] + MgO, Pt] in the temperature range 800°–1200°C. The temperature dependence of the freeenergies of formation of the ternary compounds can be represented by theequations [dformula CdO(r.s.) + Cr[sub 2]O[sub 3](cor) --> CdCr[sub 2]O[sub 4](sp)] [dformula Delta G[sup 0] = - 42,260 + 7.53T ([plus-minus]400) J] and [dformula MgO(r.s.) + Cr[sub 2]O[sub 3](cor) --> MgCr[sub 2]O[sub 4](sp)] [dformula Delta G[sup 0] = - 45,200 + 5.36T ([plus-minus]400) J] The entropies of formation of these spinels are discussed in terms of cationdisorder and extent of reduction of Cr3+ ions to Cr2+ ions. Thermodynamicdata on the chromates of cadmium and magnesium are derived by combiningthe results obtained in this study with information available in the literatureon high temperature, high pressure phase equilibria in the systems CdO-Cr2O3-O2 and MgO-Cr2O3-O2.

Gibbs free energy of formation of magnesium stannate

he thermodynamic properties of the spinel Mg2SnO4 have been determined by emf measurements on the solid oxide galvanic cell,View the MathML source in the temperature range 600 to 1000°C. The Gibbs' free energy of formation of Mg2SnO4 from the component oxides can be expressed as View the MathML source,View the MathML source These values are in good agreement with the information obtained by Jackson et al. [Earth Planet. Sci. Lett.24, 203 (1974)] on the high pressure decomposition of magnesium stannate into component oxides at different temperatures. The thermodynamic data suggest that the spinel phase is entropy stabilized, and would be unstable below 207 (±25)°C at atmospheric pressure. Based on the information obtained in this study and trends in the stability of aluminate and chromite spinels, it can be deduced that the stannates of nickel and copper(II) are unstable.

Gibbs free energies of formation of indium (III) oxide and sulphate

Emf measurements on the galvanic cell Pt, Ta, In + In,O, / Tho,-Y,03 / Cu + C+O, Pt were used to obtain the standard free energy of formation of 1%03fr om 600 to 900°C. Differential thermal analysis was used to detect the decomposition of In2(S0,), under controlled SO2 + O2 + Ar mixtures in thqtemperature range 640-8wC. X-ray diffraction analysis indicated that the decomposition product was 1%03 without an oxywlphate intermediate. The following equations were obtained for the variation of the standard free-energy change(Jlmole) with temperature: