# Tagged Questions

An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that ...

365 views

### How to check numerical precision of my computation of Stieltjes-constants?

In a thread in MSE I proposed an older routine of mine for the efficient computation of coefficients; I use a very similar routine for the quick&dirty computation of the Stieltjes-constants. ...
2k views

### How to make an approximation of path with polynom P(x,y)=0?

Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path $P(x,y)=0$ where $P(x,y)$ - is unknown polynom. May be somebody can suggest an appropriate algorithm? ...
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 (...
238 views

470 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]$) ...
579 views

### biggest cube problem (given set of bricks)

Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces. Problem: find the way of putting together those pieces to make a solid that contains biggest ...
270 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 ...
817 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$ ...
346 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 ...
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. ...