Approximating MIN 2-SAT and MIN 3-SAT

We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAX k-SAT problem. We also obtain some hardness of approximation results.     

On the approximation of protein threading

In this paper, we study the protein threading problem, which was proposed for predicting a folded 3D protein structure from an amino acid sequence. Since this problem was already proved to be NP-hard, we study polynomial time approximation algorithms. We show several hardness results for the approximation, which includes a MAX SNP-hardness result. We also show approximation algorithms for a special case and a general case, where a graph representing interactions between amino acid residues is restricted to be planar in a special case. For this special case, we obtain a constant approximation ratio.     

Approximation bounds for smooth functions in C(Rd) byneural and mixture networks

We consider the approximation of smooth multivariate functions in C(R(d)) by feedforward neural networks with a single hidden layer of nonlinear ridge functions. Under certain assumptions on the smoothness of the functions being approximated and on the activation functions in the neural network, we present upper bounds on the degree of approximation achieved over the domain R(d), thereby generalizing available results for compact domains. We extend the approximation results to the so-called mixture of expert architecture, which has received considerable attention in recent years, showing that the same type of approximation bound may be achieved.     

Approximate convolution with pairs of cubic Bézier LN curves

In this paper we present an approximation method for the convolution of two planar curves using pairs of compatible cubic Bézier curves with linear normals (LN). We characterize the necessary and sufficient conditions for two compatible cubic Bézier LN curves with the same linear normal map to exist. Using this characterization, we obtain the cubic spline approximation of the convolution curve. As illustration, we apply our method to the approximation of a font where the letters are constructed as the Minkowski sum of two planar curves. We also present numerical results using our approximation method for offset curves and compare our method to previous results.     

Automated Discovery of Numerical Approximation Formulae via Genetic Programming

This paper describes the use of genetic programming to perform automated discovery of numerical approximation formulae. We present results involving rediscovery of known approximations for Harmonic numbers, discovery of rational polynomial approximations for functions of one or more variables, and refinement of existing approximations through both approximation of their error function and incorporation of the approximation as a program tree in the initial GP population. Evolved rational polynomial approximations are compared to Padé approximations obtained through the Maple symbolic mathematics package. We find that approximations evolved by GP can be superior to Padé approximations given certain tradeoffs between approximation cost and accuracy, and that GP is able to evolve approximations in circumstances where the Padé approximation technique cannot be applied. We conclude that genetic programming is a powerful and effective approach that complements but does not replace existing techniques from numerical analysis.     

A scalable algorithm for dispersing population

Models of forest ecosystems are needed to understand how climate and land-use change can impact biodiversity. In this paper we describe an ecological dispersal model developed for the specific case of predicting seed dispersal by trees on a landscape for use in a forest simulation model. We present efficient approximation algorithms for computing seed dispersal. These algorithms allow us to simulate large landscapes for long periods of time. We also present experimental results that (1) quantify the inherent uncertainty in the dispersal model and (2) describe the variation of the approximation error as a function of the approximation parameters. Based on these experiments, we provide guidelines for choosing the right approximation parameters, for a given model simulation.     

Structure of Polynomial-Time Approximation

Approximation schemes are commonly classified as being either a polynomial-time approximation scheme (ptas) or a fully polynomial-time approximation scheme (fptas). To properly differentiate between approximation schemes for concrete problems, several subclasses have been identified: (optimum-)asymptotic schemes (ptas^∞, fptas^∞), efficient schemes (eptas), and size-asymptotic schemes. We explore the structure of these subclasses, their mutual relationships, and their connection to the classic approximation classes. We prove that several of the classes are in fact equivalent. Furthermore, we prove the equivalence of eptas to so-called convergent polynomial-time approximation schemes. The results are used to refine the hierarchy of polynomial-time approximation schemes considerably and demonstrate the central position of eptas among approximation schemes.     

Connected facility location via random facility sampling and core detouring

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems.     

Feedback arc set problem in bipartite tournaments

In this paper we give ratio 4 deterministic and randomized approximation algorithms for the Feedback Arc Set problem in bipartite tournaments. We also generalize these results to give a factor 4 deterministic approximation algorithm for Feedback Arc Set problem in multipartite tournaments.     

Bounded Approximation: A New Criterion for Dimensionality Reduction Approximation in Similarity Search

We examine the problem of efficient distance-based similarity search over high-dimensional data. We show that a promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: The approximation volume extends across the dataspace, which causes overestimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel nonlinear transformation scheme that extracts two important parameters from the data. We devise two approximation formulations, namely, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how we can derive tight bounds for the parameters and prove further results, as well as highlight insights into the problems and our proposed solutions. To demonstrate the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes.     

PASS Approximation: A Framework for Analyzing and Designing Heuristics

We introduce a new framework for designing and analyzing algorithms. Our framework applies best to problems that are inapproximable according to the standard worst-case analysis. We circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. Given our parameterized approximation, called PArametrized by the Signature of the Solution (PASS) approximation, we design algorithms with optimal approximation ratios for problems with additive and submodular objective functions such as the capacitated maximum facility location problems. We consider two types of algorithms for these problems. For greedy algorithms, our framework provides a justification for preferring a certain natural greedy rule over some alternative greedy rules that have been used in similar contexts. For LP-based algorithms, we show that the natural LP relaxation for these problems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework. In passing, we note that our results strictly improve over previous results of Kleinberg et al. (J. ACM 51(2):263–280, 2004) concerning the approximation ratio of the greedy algorithm.     

A new method for approximating blocking probability in overflow loss networks

In this paper, we present a new approximation for estimating blocking probability in overflow loss networks and systems. Given a system for which an estimate of blocking probability is sought, we first construct a second system to act as a surrogate for the original system. Estimating blocking probability in the second system with Erlang’s fixed point approximation (EFPA) provides a better estimate for blocking probability in the original system than if we were to use the conventional approach of directly using EFPA in the original system. We present a combination of numerical and theoretical results that indicate our new approximation offers a better estimate than EFPA for a certain pure overflow loss network. Moreover, we demonstrate the accuracy of our new approximation for circuit-switched networks using alternative routing. We argue that the success of our new approximation is due to its ability to utilize congestion information imbedded in overflow traffic, whereas the conventional approach fails to utilize such information.     

Estimation of Basins of Attraction for Uncertain Systems with Affine and Lipschitz Dynamics

This paper is devoted to estimation and numerical approximation of basins of attraction for a class of uncertain systems. We consider systems described by a differential equation depending of a disturbance known by its bounds. By using viability theory tools, we derive basins of attraction lower and upper estimates. We present numerical simulation results of the viability kernel algorithm to basin of attraction approximation problems.     

Planning for robotic exploration based on forward simulation

We address the problem of controlling a mobile robot to explore a partially known environment. The robot’s objective is the maximization of the amount of information collected about the environment. We formulate the problem as a partially observable Markov decision process (POMDP) with an information-theoretic objective function, and solve it applying forward simulation algorithms with an open-loop approximation. We present a new sample-based approximation for mutual information useful in mobile robotics. The approximation can be seamlessly integrated with forward simulation planning algorithms. We investigate the usefulness of POMDP based planning for exploration, and to alleviate some of its weaknesses propose a combination with frontier based exploration. Experimental results in simulated and real environments show that, depending on the environment, applying POMDP based planning for exploration can improve performance over frontier exploration.     

Adaptive Finite Element Approximation for a Constrained Optimal Control Problem via Multi-meshes

In this paper, we study adaptive finite element approximation schemes for a constrained optimal control problem. We derive the equivalent a posteriori error estimators for both the state and the control approximation, which particularly suit an adaptive multi-mesh finite element scheme. The error estimators are then implemented and tested with promising numerical results.     

A Posteriori Error Estimates of Recovery Type for Distributed Convex Optimal Control Problems

In this paper, we derive a posteriori error estimates of recovery type, and present the superconvergence analysis for the finite element approximation of distributed convex optimal control problems. We provide a posteriori error estimates of recovery type for both the control and the state approximation, which are generally equivalent. Under some stronger assumptions, they are further shown to be asymptotically exact. Such estimates, which are apparently not available in the literature, can be used to construct adaptive finite element approximation schemes and as a reliability bound for the control problems. Numerical results demonstrating our theoretical results are also presented in this paper.     

Estimation and marginalization using the Kikuchi approximation methods

In this letter, we examine a general method of approximation, known as the Kikuchi approximation method, for finding the marginals of a product distribution, as well as the corresponding partition function. The Kikuchi approximation method defines a certain constrained optimization problem, called the Kikuchi problem, and treats its stationary points as approximations to the desired marginals. We show how to associate a graph to any Kikuchi problem and describe a class of local message-passing algorithms along the edges of any such graph, which attempt to find the solutions to the problem. Implementation of these algorithms on graphs with fewer edges requires fewer operations in each iteration. We therefore characterize minimal graphs for a Kikuchi problem, which are those with the minimum number of edges. We show with empirical results that these simpler algorithms often offer significant savings in computational complexity, without suffering a loss in the convergence rate. We give conditions for the convexity of a given Kikuchi problem and the exactness of the approximations in terms of the loops of the minimal graph. More precisely, we show that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically. Together with the fact that in the cycle-free case, the iterative algorithms are equivalent to the well-known belief propagation algorithm, our results imply that, generically, the Kikuchi approximation method can be exact if and only if traditional junction tree methods could also solve the problem exactly.     

Order-reducing approximation of two-time-scale discrete linear time-varying systems

In this paper we study a two-time-scale discrete-time linear time-varying system. We heuristically find a reduced-order approximation to its asymptotic behaviour as the time-scale separation tends to infinity. This approximation results in a white noise representation of the fast state vector, and a corresponding approximation error in the slow state vector. After introducing the approximate system we define concepts of continuity and rate of variation which are needed in the discrete-time analysis. We then prove that as the time-scale separation increases, the state of the reduced-order system asymptotically coincides with the slow state of the original system in the mean-square sense on compact time intervals. We also find the order of the slow state approximation error covariance.     

Data Gathering with Tunable Compression in Sensor Networks

We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computationally intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective trade-offs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology, as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant-factor approximation for the grid topology and good average performance on the general graphs. Although, theoretically, a more complicated randomized algorithm offers a polylogarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation.     

A high order isoparametric finite element method for the computation of waveguide modes

We have studied the approximation of optical waveguide eigenvalues by a high order isoparametric vector finite element method. Isoparametric mappings are used for the approximation of domains with curved boundaries or curved material interfaces. Eigenvalue convergence for curved elements is investigated. Numerical results verify the predicted order of convergence and show the remarkable accuracy of the method.