Skip to main content
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.'s user avatar
  • 162k
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 ...
Pseudonym's user avatar
  • 22.3k
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 ...
Cort Ammon's user avatar
  • 3,351
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 ...
Markus Mottl's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Ariel's user avatar
  • 13.4k
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, ...
David Richerby's user avatar
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....
ComicSansMS's user avatar
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.'s user avatar
  • 162k
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 ...
orlp's user avatar
  • 13.6k
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 ...
Yuval Filmus's user avatar
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 ...
Ggouvine's user avatar
  • 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 ...
Yuval Filmus's user avatar
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^...
Yashas's user avatar
  • 275
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 ...
Yuval Filmus's user avatar
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 ...
djechlin's user avatar
  • 497
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\...
Ariel's user avatar
  • 13.4k
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 ...
aelguindy's user avatar
  • 1,807
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.'s user avatar
  • 162k
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.'s user avatar
  • 162k
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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\...
Christopher Boo's user avatar
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*} &...
Yuval Filmus's user avatar
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.'s user avatar
  • 162k
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}...
xskxzr's user avatar
  • 7,520
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): ...
Yuval Filmus's user avatar
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....
Acccumulation's user avatar
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 ...
Sriram's user avatar
  • 402

Only top scored, non community-wiki answers of a minimum length are eligible