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.

Filter by
Sorted by
Tagged with
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
1answer
124 views

What are good parametrizations of rational functions for response surface models?

For fitting a response surface model to a physical process, I have 3-4 relevant "signals", like a feature density, a signal based on a feature width, or a signal based on a distance to the next ...
1
vote
1answer
214 views

What is the algorithm that matlab used in its built-in function 'pca'?

Do anyone know what is the algorithm that MATLAB used in its built-in function "pca"? I have the following data set: 148.9820 55.8438 210.2150 149.3030 56.8891 208.4280 151.4400 55....
1
vote
1answer
62 views

Questions on Daubechies wavelets

Is the refinement equation for the orthonormal Daubechies scaling function $$\phi(x) = \sqrt{2} \sum_n h_n \phi(2x-n) \;?$$ The filter coefficients for Daubechies wavelets have been given e.g. in this ...
1
vote
1answer
102 views

Approximation of a non linear problem with python

I need your help to solve a problem I'm working on for school. My goal is to approximate the coefficients of a weight matrix so that they check particular properties. So I have $W$ the weight matrix ...
1
vote
1answer
71 views

Expected number of steps before a global optimum is found with Simulated Annealing

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link. Given $G=(V, E)$ is the graph ...
1
vote
1answer
72 views

Determine low-order polynomial lower bound

I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the ...
1
vote
1answer
1k views

Assigning Groups Based on Preference List [closed]

I am trying to make a system that will sort a list individuals and their preferred list of others. This may not make complete sense, but bear with me. I have a list of people, each with their list of ...
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
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
1answer
50 views

Finding optimal point distance to get desired number of random points in an area

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$: I need to control the number of points in the ...
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
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
74 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
2answers
118 views

Looking for a particular algorithm for numerical integration

Consider the following differential equation \begin{equation} p(t) = \frac{\partial q(t)}{\partial t} \end{equation} where $t \in (0,\infty)$. I have a build a code that spits out values of the ...
0
votes
2answers
3k views

Successive over-relaxation not converging (when not done in-place)

I'm trying to find the potential given some boundary conditions using the successive over-relaxation method. I have 2 solutions: -One iterates over all elements and applies the formula ...
0
votes
2answers
101 views

How can I calculate the exponential integral?

(I originally asked this in a different exchange.) I'm writing a program that uses the prime-counting function. Right now, I'm using x/log(x), but I want to ...
0
votes
1answer
203 views

Linear Least-Squares Point-to-Plane ICP degenerative case

I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
0
votes
2answers
387 views

closed form approximation of matrix inverse with special properties

I'm trying to find some theory to help me explicitly express the inverse of a matrix (or a close approximation of the inverse). My matrix has the following properties: invertible positive definite ...
0
votes
1answer
42 views

Slightly change two vectors to satisfy a constraint

$\vec{a}\cdot\vec{b} \approx c$ $\vec{\alpha} \cdot \vec{\beta} = c$ $\vec{\alpha}$ is close to $\vec{a}$ and $\vec{\beta}$ is close to $\vec{b}$ Given $\vec{a}$, $\vec{b}$ and c, how to find $\vec{\...
0
votes
1answer
78 views

Which are some good algorithms and heuristics to calculate the similarity between two matrices?

Say I have a matrix like this: \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} And this one: \begin{bmatrix} ...
0
votes
1answer
205 views

B-Splines Matlab Package

I'm looking for a good Matlab package/library for B-Splines approximation. Ideally, it would take knots $t_1, \ldots , t_n$, and data points $g(t_1),\ldots , g(t_n)$, and Produce $$Vg :\,= \sum\...
0
votes
1answer
90 views

what is non-asymptotic convergence?

I guess convergence in general means it is in asymptotic sense but what does non-asymptotic convergence mean?. Can someone please explain with an example?
0
votes
1answer
53 views

Chebychev Polynomial derivatives at zero points and extreme points

I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression, $$ T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x) $$ has the derivative $$ T'_{j+1}(x) = 2T_j(...
0
votes
1answer
284 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
0
votes
1answer
45 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
1answer
1k views

Derivatives of a Chebychev polynomial

I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ...
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 ...
-1
votes
1answer
403 views

Finite Difference for Fourth-Order PDE

How to discretize the following 4th order PDE using finite difference method? $$\frac{\partial^{2} y}{\partial t^{2}}+\frac{\partial^{4} y}{\partial x^{4}}=0$$ thanks

1
2