# Questions tagged [approximation]

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

175 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
156 views

### Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
198 views

### Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
89 views

136 views

### Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
87 views

### Different properties of Heavy-Hitters and Count-Min Sketch algorithms?

I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
113 views

### An approximation for the sum of k largest elements of n-sorted arrays?

Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements. All elements are between 0 and 1, and the the sum of all elements in array $i$...
57 views

### Hardness of approximation for online algorithms

Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds ...
526 views

### Why is there no FPTAS for the maximum independent set problem?

I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$. I found the following approach after some ...
40 views

### Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?

I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit ...
64 views

### Why this set cover greedy-like algorithm is not $\log k$-approximation for bin packing problem?

Bin packing: Given a set of $k$ items where item $j$ has size $s_j$ and a set of bins of capacity $C$ each. Use the minimum number of bins to pack all items while respecting the capacity of the used ...
I have been so confused for a while!! Please help me with this, thank you very much in advance!! Given hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set \$...