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
5
votes
0answers
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 ...
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
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 ...
4
votes
0answers
138 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
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 ...
3
votes
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 $\...
2
votes
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 ...
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
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 ...
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
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 ...
2
votes
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, ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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}\...
1
vote
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 ...
1
vote
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 ...
0
votes
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)~~~~~~(...
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 ...