# 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.

84 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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, ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
50 views

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} ...
205 views

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\... 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? 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(...
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 ...