# 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 ...

### 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 ...
Accepted

### PTAS definition vs. FPTAS

Let me answer your questions in order: By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial ...

### 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 ...
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 ...

### What is a bicriteria approximation algorithm?

I'll expand on the answer by Yuval Filmus by providing an interpretation based on multi-objective optimization problems. Single-objective optimization and approximation In computer science we often ...

### 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 ...