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.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
221 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 ...
5
votes
0answers
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 ...
4
votes
0answers
52 views

Continuous limit and nonlinear functional analysis

I have a kind of general question about approximation schemes in nonlinear functional analysis. Given a nonlinear map $\Phi$ from an open set (in an infinite dimensional Banach space) of functions to ...
4
votes
0answers
72 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 ...
4
votes
0answers
167 views

MATLAB: Compute the Schwarz-Christoffel transformation symbolically

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 - ...
4
votes
0answers
84 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 ...
3
votes
0answers
154 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 $\...
2
votes
0answers
87 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 ...
2
votes
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 ...
2
votes
0answers
58 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 ...
2
votes
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 ...
2
votes
0answers
99 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 ...
2
votes
0answers
194 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, ...
1
vote
0answers
65 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 ...
1
vote
0answers
56 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 ...
1
vote
0answers
37 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 ...
1
vote
0answers
47 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 ...
1
vote
0answers
50 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}\...
1
vote
0answers
76 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 ...
1
vote
0answers
130 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 ...
0
votes
0answers
77 views

Boundary conditions for an FEM approximation of the Laplace operator

Using FEM, I want to approximate the Laplacian $$u = \nabla \cdot \nabla h \, ,$$ where $h(x,y)$ is an FEM approximated scalar field on the same mesh, i.e. piecewise differentiable. I am using MOOSE ...
0
votes
0answers
27 views

Computing square root of rank-1 correction

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 ...
0
votes
0answers
65 views

approximation of nonlinear time-dependent system with history

I have two time-dependent coupled equations. One of which is several orders of magnitude more computationally demanding than the other. I am trying to use machine learning to reproduce the behavior of ...