# Questions tagged [approximation]

A method of finding nearly-optimal solutions to a problem. Generally, this terminology is applied to algorithms and heuristics for solving NP-Hard problems in computer science.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
200 views

### What algorithm does (or did?) Excel use for Bessel functions that is discontinuous at x=8?

Writing this comment reminded me of something I noticed years ago about evaluating Bessel functions of the first kind $J_n(x)$ in Excel. (BESSELJ) I don't use Excel now but at the time I'd checked ...
127 views

### Are there any benefits of computable analysis to numerical algorithms

Computers can work only with computable numbers, while most of the algorithms are based on analysis of real numbers (real analysis). When I heard of the existence of computable analysis I ...
70 views

### Fast approximate solver for vehicle routing problem

I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
138 views

Suppose we have a conformal mapping from the unit disk in the $\omega$ plane onto the exterior of a polygon in the $z$ plane. The Schwarz-Christoffel mapping in this case is defined as: $$f(u) = A - ... 0answers 83 views ### Extrapolation after successive finite element refinement I wish to compute a certain function \lambda (in my case an eigenvalue of the Laplacian) to a certain accuracy, which I wish to guarantee, if possible. I started with a finite element method. I know ... 0answers 153 views ### Reference Request: Variational Problem I want to solve approximately the following variational problem: Given a function c:[-1,1]^2\rightarrow [0,1], constants p_1...p_n\in \mathbb{R}^+, \alpha_1...\alpha_n\in \mathbb{R}, and \... 0answers 76 views ### Remez algorithm convergence I have implemented the Remez algorithm in Python where all calculations were done with the Python mpmath library. I have noticed that sometimes the |E_{max}| and |E_{min}| do not monotonically ... 0answers 28 views ### Fast approximate evaluation of Fourier-Legendre series Suppose I know that a function from [0,\pi] \to \mathbb{R} may be written as$$ \sum_{k=0}^\infty A_l \frac{2l+1}{4\pi} P_l(r) $$where A_l all are known. Is there a way in which I may very ... 0answers 56 views ### Weighted Set Cover in practice, beyond the greedy algorithm According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ... 0answers 92 views ### Finding most efficient route (distance/number of nodes) that uses nodes at least X amount away from another node I'm trying to find the "looped" route with the lowest value of D/n, where D=Distance, and ... 0answers 97 views ### Algorithm for optimizing graph interconnectivity I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ... 0answers 192 views ### Good approximate solutions for a MILP problem The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi. For mid-sized cities, ... 0answers 63 views ### Error curve does not oscillate in between reference points using Remez Using the Remez algorithm, implemented using multi-precision library, in certain functions that I want to approximate, the error curve does not oscillate in between reference points, and so no roots ... 0answers 53 views ### Computing dilogarithm I'm measuring the integral of a quantity which, mathematically, requires the computation of a dilogarithm function.$$\operatorname{Li}_2(be^{ax})$$where b and a (are real and) can be positive ... 0answers 35 views ### Find alternative path closest to original I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ... 0answers 45 views ### Alternative to two “for” loops in finding best neighborhoods for TSP? I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!). For the moment I am using ... 0answers 49 views ### A better way to compute a double integral involving a infinite series? Let D_{\nu}(.) is the parabolic cylinder function (http://mathworld.wolfram.com/ParabolicCylinderFunction.html) And \Gamma(.) is the Gamma function. Define s_y(\mu,\nu,t,z)=2^{\nu}\... 0answers 68 views ### Piecewise linear fitting of a curve in loglog plot Iam basically trying to fit a curve similar to that shown in fig (a) with 7 straight line segments (ie. 6 knots) as shown in fig (b) and I need to get the optimum knot positions. This is a tripartite ... 0answers 129 views ### Quadratic programming problem involving permutation matrices Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices A and B, minimize \| P A P^\top - B \| over all permutation ... 1answer 36 views ### Linearization of Remez algorithm rational case In the rational case, we are interested to find polynomials P(x) and Q(x) s.t. f(x_k)-P(x_k)/Q(x_k)=(-1)^kE for k=1,2,\ldots, N where N=deg(P)+deg(Q)+2 This can be rewritten as$$ (1)~~~~~~(...
In the post Computing square root of diag(u)-uu'?, both @YaroslavBulatov and @NickAlger suggested the factor $\frac{\sqrt{u^{T}D^{-1}u+1}-1}{u^{T}D^{-1}u}$ for their approximation. Can somebody ...