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.♦
- 166k
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 ...
- 23.8k
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,369
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
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.6k
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, ...
- 82.2k
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
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.9k
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 ...
- 485
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 ...
- 279k
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
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.♦
- 166k
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,817
5
votes
Accepted
Correctness proof: 2-approximation of greedy matching-algorithm
Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching).
For all $e\in M'$ let $M_e\...
- 13.6k
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 ...
- 497
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.♦
- 166k
5
votes
Accepted
Maximum cut using a 1/2 approximation greedy algorithm
Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the ...
- 279k
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 ...
- 279k
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\...
- 484
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*}
&...
- 279k
5
votes
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 ...
D.W.♦
- 166k
5
votes
Accepted
Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}...
- 7,604
5
votes
Meaning of "approximation within $n^{1−\epsilon}$"
It is unfortunate that papers in hardness of approximation use this kind of phrasing, since it is rather inaccurate. Here is what the paper actually proves (see the proof of Theorem 1.2 on page 118):
...
- 279k
5
votes
What is the fastest algorithm to approximate an irrational number with specified precision?
Well, $O(k\log10) = O(k) = O(k\log_210)$, and $k\log_210$ is the amount of bits of information needed, so if you have a process that can only return $1$ bit per query, you'll need that many queries....
- 710
5
votes
Accepted
Applicability of approximation algorithms vs meta-heuristics in practice
Well, practitioners, as far as I have noticed, do not show a very stark difference between heuristics and approximation algorithms.
The upside that the approximation algorithms community provides with ...
- 387
4
votes
Accepted
Analysis of a randomized algorithm for independent set construction
You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then
\begin{align}
\...
- 816
4
votes
Accepted
Maximizing the boolean combination of given real numbers
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:
set $b_i=1$ if $x_i > 0$
set $b_i=0$ if $x_i < 0$
all others $...
- 348
4
votes
Accepted
Why is the inapproximability $2^{n^\epsilon}$?
The two theorems are equivalent. You can write
$$
3^{n^\delta} = 2^{\log_2 3 \cdot n^\delta} = 2^{n^{\delta + \frac{\log \log_2 3}{\log n}}} = 2^{n^{\delta + o(1)}}.
$$
In particular, for any $\delta' ...
- 279k
4
votes
Accepted
How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?
After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and a graph $...
- 534
Only top scored, non community-wiki answers of a minimum length are eligible