The approximation-algorithms tag has no usage guidance.

**0**

votes

**0**answers

158 views

### Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that
...

**1**

vote

**0**answers

70 views

### An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label).
We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...

**3**

votes

**0**answers

238 views

### Place n telescopes on a sphere in R^d to see the whole sky

Where would one put $n$ telescopes on the surface of the earth
to see the whole sky as well as possible ?
Use the cosine metric to define how well we can see in direction $x$:
$ \qquad \text{cansee}( ...

**8**

votes

**0**answers

446 views

### How to evaluate binomial coefficients efficiently and as correctly as possible?

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer.
The reason why I ask is ...

**1**

vote

**0**answers

229 views

### Multiobjective semidefinite programming

Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...

**1**

vote

**0**answers

465 views

### Representing vertices of a cube using linear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...

**5**

votes

**2**answers

560 views

### Getting started: combinatorial optimization for computer scientists

I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems.
I have good knowleges of graphs, *-flow algorithms and so ...

**0**

votes

**0**answers

112 views

### sparsest cut always has solution

Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...

**5**

votes

**0**answers

251 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

**3**answers

385 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

**0**answers

332 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

2k 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. ...

**1**

vote

**2**answers

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

**3**

votes

**0**answers

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

**2**

votes

**2**answers

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

**6**

votes

**3**answers

871 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:
...

**0**

votes

**1**answer

6k 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 ...

**4**

votes

**1**answer

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