# Questions tagged [approximation]

Questions about algorithms that solve problems up to some bounded error.

550 questions
Filter by
Sorted by
Tagged with
1 vote
52 views

1 vote
27 views

### Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
• 37
36 views

### Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
• 2,871
63 views

### approximation ratio of TSP problem where the weights are bounded by an inequality

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time ...
• 369
17 views

### Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?

So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if : $A \geq opt(1-\epsilon) \; ,\forall \epsilon > 0$ (and I guess ...
• 201
1 vote
43 views

• 111
1 vote
30 views

### Embedding from $L^\infty$ space to $L^2$ space

I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ ...
• 196
78 views

### What is an O(n)-approximation?

I see the following notations used: $O(1)$-approximation $O(n)$-approximation $\Omega(n)$-approximation Can someone please explain what they mean? I know what an approximation is with a normal ...
• 298
35 views

• 137
40 views

### Failing to calculate the gradient and y-shift for best fit line using sum-squares method. Can anyone help me to pinpoint the issue?

I'm trying to work out how to make the working implementation of fitting the straight line among the set data points. I base my function: ...
• 103
1 vote