# Tag Info

Accepted

### Why there are no approximation algorithms for SAT and other decision problems?

Approximation algorithms are only for optimization problems, not for decision problems. Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to ...
Accepted

Accepted

### Does #$P$-Completeness imply approximation hardness?

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ . (In the model he ...
Accepted

### Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon > 0$ then P=NP. This is because for every $\epsilon > 0$ there is a polytime ...

### What is inapproximability of NP-hard problems?

Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely ...

### Better results for minimum vertex cover algorithms

A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the ...
Accepted

### MAXSAT approximation

I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, ...

### Approximating the Kolmogorov complexity

Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses ...

### Why there are no approximation algorithms for SAT and other decision problems?

In addition to the existing answers, let me point out that there are situations where it makes sense to have an approximate solution for a decision problem, but it works different than you might think....

### What is a bicriteria approximation algorithm?

Often, an optimization problem involves several parameters. For example, consider the problem of graph partitioning. Given a weighted graph, an integer $k$, and a parameter $\rho$, we want to ...

### Algorithm to distribute items "evenly"

This "smells" like it might be NP-hard. So, what do you do when you have a NP-hard problem? Throw a heuristic at it, or an approximation algorithm, or use a SAT solver. In your case, if you don't ...

### Knapsack Greedy Approximation: Worst Case

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been ...
Accepted

### Approximation ratio when optimal solution is $0$

That's right. Such a problem is not approximable to within any constant factor large than 1 (unless P=NP). Is there a way around this? Yes, there are several possibilities: Use a different measure ...
Accepted

### Is this partitioning problem NP-complete?

This problem can be solved in polynomial time with dynamic programming. Let $A[i]$ be the maximum value you can achieve with the points $x_1, \dots, x_i$. You can compute $A[i]$ by choosing the ...

### Why are NP-complete problems so different in terms of their approximation?

As an intuitive approach, consider that instantiations of NP-complete problems are not always as hard as the general case. Binary satisifiability (SAT) is NP-complete, but it's trivial to find the ...
Accepted

### How to give an approximation algorithm for this unusual bin packing problem?

Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the ...
Accepted

### Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$...

### Meaning behind 1/ϵ in FPTAS

Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation ...
An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the ...