35

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


15

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


15

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


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


12

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


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


11

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


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

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


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

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 $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), ...


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

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

Of course, if you round, you have to verify that rounding preserves feasibility. Let us for example consider the relaxed VERTEX-COVER LP formulation. $$ \begin{array}{lll} \text{min} & \sum_{v\in V}c(v)x_v & \\ \text{s.t.} &x_u+x_v\ge1, & \quad (u,v)\in E \\ &x_v\ge 0. & \quad v\in V \end{array} $$ It is known that the solution to ...


7

Yes, at least under some reasonable assumptions. Crescenzi, Kann, Silverstri & Trevisan show that Minimum Bin Packing, Mininum Degree Spanning Tree and Minimum Edge Coloring are APX-intermediate unless the polynomial hierarchy collapses. Considering that the paper is from 1996, I'm sure there's now a significantly larger number of known APX-intermediate ...


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