36
votes
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 ...
D.W.♦
- 154k
19
votes
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 ...
- 21.3k
17
votes
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 ...
- 274k
15
votes
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,243
13
votes
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
11
votes
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 ...
- 255
11
votes
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 ...
- 274k
10
votes
Accepted
Why is Savage's Vertex Cover algorithm a 2-approximation?
First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.
Next, we show that the DFS tree has a matching of size at least $|...
- 274k
9
votes
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 ...
- 274k
9
votes
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.3k
9
votes
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, ...
- 81.4k
8
votes
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
7
votes
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 ...
D.W.♦
- 154k
7
votes
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 ...
- 12.6k
6
votes
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$...
- 274k
6
votes
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 ...
- 274k
6
votes
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 ...
- 475
6
votes
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 ...
- 274k
6
votes
fast and stable x * tanh(log1pexp(x)) computation
With some algebraic manipulation (as pointed out in @orlp's answer), we can deduce the following:
$$f(x) = x \tanh(\log(1+e^x)) \tag{1}$$
$$ = x\frac{(1+e^x)^2 - 1}{(1+e^x)^2 + 1} = x\frac{e^{2x} + 2e^...
- 275
5
votes
Why are PTAS-Reductions used to establish APX-Hardness?
Let me correct two misconceptions in your question:
$PTAS$-reductions are approximation-preserving
$APX$ is the class of problems that have constant-factor approximations
The big open question isn't ...
- 13.1k
5
votes
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 ...
- 274k
5
votes
Accepted
Clarification on the inapproximability of set cover
The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection ...
- 274k
5
votes
Accepted
What does $\mathbf{Q}^+$ mean in approximation texts?
I'm going to say yes, positive rationals, because:
That's what it means throughout math literature.
That's a sensible domain for a cost function. It would possibly be a different algorithm problem if ...
- 487
5
votes
Accepted
Heuristic algorithms for the dense assignment problem
This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all ...
- 1,787
5
votes
Confused between turing-completeness and universal approximation - are they related?
A CNN can approximate a function on a fixed number of input variables, say $n$ of them. The set of functions on $n$ input variables isn't "Turing-complete". For instance, a boolean function $f:\{0,1\...
D.W.♦
- 154k
5
votes
Looping and branching with Algorithmic Differentiation
If you want the derivative everywhere, automatic differentiation can't handle branches and loops. If you are satisfied with getting the derivative "almost everywhere", automatic differentiation might ...
D.W.♦
- 154k
5
votes
Definition of $\alpha$-approximation
There are actually two main types of approximation algorithms: those that return an approximate solution, and those that return the approximate value. In order to explain the difference, let me define ...
- 274k
5
votes
Closest-point heuristic approximation problem
I think there's some problem with the LaTeX formula. It should look like this:
$c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$
Let's say initially it was $u\to x$. Then you add $v$ directly after $u$, forming $u\...
- 474
5
votes
Accepted
Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?
The MAX-CUT algorithm relies on semidefinite programming, a convex optimization problem which can be solved in polynomial time. What you solve directly is the semidefinite program
$$
\begin{align*}
&...
- 274k
Only top scored, non community-wiki answers of a minimum length are eligible