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 ...
user avatar
  • 141k
28 votes
Accepted

What is the fastest algorithm to approximate an irrational number with specified precision?

You are in fact asked to find $b$ independent bits of information (such that $2^{-b}\sim10^{-k}$)*, using queries that return a single bit of information each. So you can't get an answer in less than $...
user avatar
  • 3,912
17 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 ...
user avatar
  • 18.9k
16 votes
Accepted

PTAS definition vs. FPTAS

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 ...
user avatar
15 votes

What does the 2 in a 2-approximation algorithm mean?

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 ...
user avatar
  • 22.1k
15 votes
Accepted

Why are NP-complete problems so different in terms of their approximation?

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....
user avatar
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 ...
user avatar
  • 3,085
14 votes

Why are NP-complete problems so different in terms of their approximation?

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 ...
user avatar
13 votes

Algorithm to distribute items "evenly"

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 ...
user avatar
11 votes

What is a bicriteria approximation algorithm?

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 ...
user avatar
11 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 ...
user avatar
10 votes
Accepted

Why is Savage's Vertex Cover algorithm a 2-approximation?

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 $|...
user avatar
9 votes
Accepted

Does #$P$-Completeness imply approximation hardness?

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 ...
user avatar
9 votes
Accepted

Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

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 ...
user avatar
9 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 ...
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 ...
user avatar
  • 13.2k
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, ...
user avatar
8 votes

Approximating the Kolmogorov complexity

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 ...
user avatar
  • 1,475
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....
user avatar
7 votes

What is a bicriteria approximation algorithm?

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 ...
user avatar
7 votes

Algorithm to distribute items "evenly"

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 ...
user avatar
  • 141k
7 votes

Knapsack Greedy Approximation: Worst Case

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 ...
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 12.3k
6 votes

Why are NP-complete problems so different in terms of their approximation?

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 ...
user avatar
  • 3,085
6 votes
Accepted

How to give an approximation algorithm for this unusual bin packing problem?

Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the ...
user avatar
6 votes
Accepted

Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$...
user avatar
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 ...
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 ...
user avatar
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 ...
user avatar

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