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


16

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


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


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


13

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


13

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


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

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

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


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

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

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


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

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

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

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


8

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, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (...


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


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

Often, an optimization problem involves several parameters. For example, consider the problem of graph partitioning. Given a weighted graph, an integer $k$, and a parameter $\rho$, we want to partition the vertex set into $k$ parts $V_1,\ldots,V_k$ of size at most $\rho$ while minimizing the number of cut edges $E(V_1,\ldots,V_k)$ (edges connecting vertices ...


7

This "smells" like it might be NP-hard. So, what do you do when you have a NP-hard problem? Throw a heuristic at it, or an approximation algorithm, or use a SAT solver. In your case, if you don't need the absolute optimal solution, one reasonable starting point might be to try simulated annealing. There is a natural way to take any candidate solution and ...


7

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that $$ p_1 + \cdots + p_{k-1} +...


7

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 maximum of $A[k]$ + $f(x_{k+1}, x_{k+2}, \dots, x_i)$ from all $k < i$. Then $A[n]$ contains your answer.


6

As an intuitive approach, consider that instantiations of NP-complete problems are not always as hard as the general case. Binary satisifiability (SAT) is NP-complete, but it's trivial to find the solution to A v B v C v D v ... The complexity algorithms just bound the worst-case, not the average case, or even the 90% case. The easiest way to reduce a NP-...


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