# 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 ...
• 162k

### What is the fastest algorithm to approximate an irrational number with specified precision?

Let's suppose for a moment that instead of finding a decimal expansion, you're trying to find a binary expansion; you want to find the irrational number to $k$ binary places. Then the information ...
• 22.3k

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

The reason you don't see things like approximation ratios in decision making problems is that they generally do not make sense in the context of the questions one typically asks about decision making ...
• 3,351
Accepted

### Looping and branching with Algorithmic Differentiation

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be ...
• 246

### 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 ...
• 278k

### 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 ...
• 13.4k
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, ...

### 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....
• 294
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 ...
• 162k
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 ...
• 13.6k

### 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 ...
• 278k

### Better results for minimum vertex cover algorithms

Although, as posted by Ariel, there is no known way to obtain theoretically better results, there are many ways to improve on it in practice. A typical technique is a local search algorithm, that ...
• 485

### What is an approximation oracle?

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 ...
• 278k

• 278k
Accepted

### Equivalent Colorings of Graphs

Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices. So, here is one plausible algorithm you could use: We are given an existing coloring $C$. Pick ...
• 162k
Accepted