The approximation-algorithms tag has no wiki summary.

**5**

votes

**0**answers

235 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**4**

votes

**1**answer

789 views

### Searching for an inhomogeneous diophantine approximation algorithm

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, what is an algorithm that will provide coprime integers $a$ ...

**0**

votes

**0**answers

315 views

### Approximate a piecewise linear path by a path with bounded curvature

I have a piecewise linear path in two dimensions (with finitely many pieces). I would like to approximate it by a curve whose radius of curvature is bounded away from 0 (i.e. I specify the bound a ...

**1**

vote

**2**answers

1k views

### Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...

**4**

votes

**2**answers

416 views

### Set Cover:Greedy vs LP

Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks

**3**

votes

**0**answers

195 views

### Algorithm for testing satisfiable fraction of linear equations mod 2

Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...

**1**

vote

**2**answers

322 views

### Approximation of conformal mapping as a sum of elementary conformal mappings

Hi,
I would like to approximate any 2d conformal mapping, as a sum of elementary conformal mappings. So I would have some basis, a conformal mapping with some parameters, and by adding several ones ...

**5**

votes

**2**answers

517 views

### Runge-Kutta method with c<1

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...

**6**

votes

**3**answers

865 views

### Approximating e with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible?
For example:
...

**4**

votes

**3**answers

382 views

### Approximating derivatives between gridpoints

Hi,
Suppose we have a grid (possibly irregular) of N function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more).
What would be a good way ...

**0**

votes

**1**answer

4k views

### HOW TO Generate Equation of a Curve Given (x,y) pairs - algorithm? [closed]

Hi,
How can I generate the equation of a curve that matches all arbitrarily given (x,y) pairs? I would like a polynomial of nth degree, where n does not matter, as long as the curve passes thru all ...

**1**

vote

**2**answers

652 views

### Approximate Algorithms for Poisson's Equation (PDE)

Are there some approximate or randomised algorithms to numerically solve Poisson's Equation in Partial Differential Equations.(http://en.wikipedia.org/wiki/Poisson%27s_equation). The best algorithms I ...

**4**

votes

**1**answer

637 views

### Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...

**1**

vote

**2**answers

1k views

### Analyzing Weighted Set-Cover variant

A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for ...