33

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 solve some decision problem? Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be ...


27

As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems. One way of doing this is to have two new classes NPO and PO that contain optimizations problems and they mimic of course the classes NP and P for decision problems. New ...


19

Usually what's shown is the NP-hardness of a "Gap" version of the problem. For example, suppose that you want to show that it's hard to approximate SET COVER to within a factor of 2. You define the following "promise" instance of SET COVER that we'll call 2-GAP-SET-COVER: Fix some number $\ell$. 2-GAP-SET-COVER consists of all instances of set cover where ...


14

The expression "$A(L) \le (1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$" is, as usual, shorthand for the following: There exist constants $c>0$ and $\varepsilon_0>0$ such that for all $\varepsilon$ with $0<\varepsilon<\varepsilon_0$, the inequality $A(L) \le (1 + \varepsilon) \text{Opt}(L) + c/\varepsilon^2$ holds.


14

There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an fptas1: an $\varepsilon$-approximation running in time bounded by $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There's a more general class $\mathrm{EPTAS}$ which relaxes the time bound to $f(\frac{1}{\...


14

One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete: $\Pi$ is in NP, and For every other problem $\Xi$ in NP, we can turn an ...


14

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 in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for ...


14

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 problems. In an optimization setting, it makes sense because it's useful to be "close." In many environments, it doesn't make sense. It doesn't make sense to ...


13

One way to consider the difference between decision version and optimization version is by considering different optimization versions of the same decision version. Take for example the MAX-CLIQUE problem, which is very hard to approximate in terms of the usual parameter – the size of the clique. If we change the optimization parameter to the logarithm of ...


11

I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation. I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," _IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005. The table lookup is indexed with the $...


11

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 study optimization problems with a single objective (for example, minimize f(x) subject to some constraint). When proving, say, NP-completeness, it is common to ...


10

A heuristic is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a proof it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a plausible idea, that should not give a too bad solution. In this case, it can be shown ...


10

In theoretical computer science, an approximation algorithm is an algorithm that guarantees a certain approximation ratio $\rho$, and an approximation scheme is a (uniform) collection of algorithms that guarantees several different approximation ratios. Since the collection is uniform (all the algorithms look the same but with different parameters), you can ...


10

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition ...


9

I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of ...


9

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.) Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #...


9

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 reduction $f_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that: If $\varphi$ is satisfiable then $...


9

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 calculated (or variables depending on them). Here is an example: if x = 3 then 9 else x * x At close inspection you will recognize that the above is really just ...


8

In his famous paper, Håstad shows that it is NP-hard to approximate MAX2SAT better than $21/22$. This likely means that is is NP-hard to distinguish instances which are $\leq \alpha$ satisfiable and instances which are $\geq (22/21) \alpha$ satisfiable, for some $\alpha \geq 1/2$. Now imagine padding an instance so that it becomes a $p$-fraction of a new ...


8

Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI): Input: Two graphs $G_0$ and $G_1$ with $n$ vertices each. Output: Accept if and only if $G_0$ and $G_1$ are not ...


8

In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge ...


8

You made a crucial change to the question. I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well. To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot. Here are some ...


8

I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well. If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you ...


8

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 analogous. Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following: If there is a polynomial time ...


8

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. With these algorithms, only one of the two outcomes is determined with certainty, while the other might be incorrect. Take the Miller-Rabin test for prime ...


8

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 input). This is what is known so far: The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ [1]. VC is ...


7

Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses it in $-\log p(x)$ bits (round up if you object to fractional bits). This means pretty much any generative machine learning algorithm can be used. This is why ...


7

Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no PTAS for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an ...


7

Kann's online compendium of NPO problems is a good place to start. Feedback Arc Set (the "Directed part is redundant when you use "arc") is: APX-hard, Approximable within $\mathcal{O}(\log n \log \log n)$ (where $n$ is the number of vertices). The problem is also fixed-parameter tractable1, so it might make more sense to solve the problem exactly, rather ...


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