Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Unified Galerkin- and DAE-Based Approximation of Fractional Order Systems

We consider numerical solutions of nonlinear multiterm fractional integrodifferential equations, where the order of the highest derivative is fractional and positive but is otherwise arbitrary. Here, we extend and unify our previous work, where a Galerkin method was developed for efficiently approximating fractional order operators and where elements of the present differential algebraic equation (DAE) formulation were introduced. The DAE system developed here for arbitrary orders of the fractional derivative includes an added block of equations for each fractional order operator, as well as forcing terms arising from nonzero initial conditions. We motivate and explain the structure of the DAE in detail. We explain how nonzero initial conditions should be incorporated within the approximation. We point out that our approach approximates the system and not a specific solution. Consequently, some questions not easily accessible to solvers of initial value problems, such as stability analyses, can be tackled using our approach. Numerical examples show excellent accuracy. DOI: 10.1115/1.4002516]

Activation barriers for d.c. conductivity in ionic glasses: Classical calculations using the small-cluster approximation

A small-cluster approximation has been used to calculate the activation barriers for the d.c. conductivity in ionic glasses. The main emphasis of this approach is on the importance of the hitherto ignored polarization energy contribution to the total activation energy. For the first time it has been demonstrated that the d.c. conductivity activation energy can be calculated by considering ionic migration to a neighbouring vacancy in a smali cluster of ions consisting of face-sharing anion polyhedra. The activation energies from the model calculations have been compared with the experimental values in the case of highly modified lithium thioborate glasses.

Phase diagram of the two-dimensional disordered Hubbard model in the Hartree-Fock approximation

Ground-state properties of the two-dimensional Hubbard model with point-defect disorder are investigated numerically in the Hartree-Fock approximation. The phase diagram in the p(point defect concentration)-delta(deviation from half filling) plane exhibits antiferromagnetic, spin-density-wave, paramagnetic, and spin-glass-like phases. The disorder stabilizes the antiferromagnetic phase relative to the spin-density-wave phase. The presence of U strongly enhances the localization in the antiferromagnetic phase. The spin-density-wave and spin-glass-like phases are weakly localized.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Decoupled three-dimensional finite element computation of thermoelastic damping using Zener's approximation

We consider three dimensional finite element computations of thermoelastic damping ratios of arbitrary bodies using Zener's approach. In our small-damping formulation, unlike existing fully coupled formulations, the calculation is split into three smaller parts. Of these, the first sub-calculation involves routine undamped modal analysis using ANSYS. The second sub-calculation takes the mode shape, and solves on the same mesh a periodic heat conduction problem. Finally, the damping coefficient is a volume integral, evaluated elementwise. In the only other decoupled three dimensional computation of thermoelastic damping reported in the literature, the heat conduction problem is solved much less efficiently, using a modal expansion. We provide numerical examples using some beam-like geometries, for which Zener's and similar formulas are valid. Among these we examine tapered beams, including the limiting case of a sharp tip. The latter's higher-mode damping ratios dramatically exceed those of a comparable uniform beam.

Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes

We develop in this article the first actor-critic reinforcement learning algorithm with function approximation for a problem of control under multiple inequality constraints. We consider the infinite horizon discounted cost framework in which both the objective and the constraint functions are suitable expected policy-dependent discounted sums of certain sample path functions. We apply the Lagrange multiplier method to handle the inequality constraints. Our algorithm makes use of multi-timescale stochastic approximation and incorporates a temporal difference (TD) critic and an actor that makes a gradient search in the space of policy parameters using efficient simultaneous perturbation stochastic approximation (SPSA) gradient estimates. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal policy. (C) 2010 Elsevier B.V. All rights reserved.