# Questions tagged [approximation]

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

507 questions
Filter by
Sorted by
Tagged with
34 views

22 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: ...
18 views

### Textbook proofs for approximation algorithms for scheduling

I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) ...
30 views

### Approximation classes for optimization problems with real values

Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.? If my understanding is correct a ...
52 views

### Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
30 views

### Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between: The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be ...
28 views

### Polynomial and fully polynomial time approximation scheme

How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program? Is there any other way to decide?
45 views

### How is "expected approximation ratio" defined in cases when the expected value of the optimal solution is known?

Consider an approximation algorithm which does better than $f(n)$, in expectation. Suppose we know that $\mathbb{E}(OPT)=g(n)$. Given that we use the convention of "larger divided by smaller"...
98 views

### What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
34 views

### Fast text comparison algorithm for long texts

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
15 views

### Voice activation keywords algorithms on iot devices?

I've been scouting the internet for days and after a lot of digging, I decided to resort to my last hope and ask: I'm talking about the "hey Google", "Alexa" and so on voice ...
106 views

28 views

### How are matchings a lower bound for an approximate vertex cover?

I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover. They mention that the 2-approximation ratio is a lower bound. How is a maximal matching ...
31 views

### Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, ...
19 views

### Can you have an approximation that is higher than the optimal for a maximum value and a lower than the optimal for a minimum value?

I was reading this page on approximation ratios and the author says that for a problem looking for a: maximum, an approximation algorithm will give us a value lower than this optimal maximum minimum, ...
22 views

### Are disjoint edges the same as matchings?

I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings. To support this, I am also watching ...
113 views

### Where does 1.3606 approximation ratio come from for vertex cover approximation?

I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm. Later, the professor asks if we can do any better. The lecturer went on to say that ...
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $... 1answer 49 views ### k-center problem: proof for Gon algorithm gives a 2-approximation The$k$-center problem is where we a given a graph$G(V,E)$, an integer$k$, a distance metric$d$and we want to find a subset$C\subseteq V$(such that$|C|\leq k$) which minimizes the following ... 1answer 60 views ### Clique is NP hard to approximate up to$n^{a}$for some$a \in (0,1)$Given that$\mathsf{NP}=\mathsf{PCP}_{[\frac{1}{n},1]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$, show that it is NP-hard to approximate clique up to factor of$n^a$for some$a \in (0,1)...
Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$? The scenario is: I have a ...