Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
549
questions
40
votes
3
answers
5k
views
Decision problems vs "real" problems that aren't yes-or-no
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
- 20.4k
31
votes
7
answers
39k
views
Algorithm to distribute items "evenly"
I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
- 433
23
votes
3
answers
2k
views
Why are NP-complete problems so different in terms of their approximation?
I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory.
One thing that I've noticed is that while many problems are NP-complete, when ...
- 505
23
votes
3
answers
2k
views
Approximating the Kolmogorov complexity
I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (...
- 333
22
votes
0
answers
512
views
Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
- 321
19
votes
3
answers
3k
views
Why there are no approximation algorithms for SAT and other decision problems?
I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the ...
- 673
18
votes
2
answers
12k
views
14
votes
1
answer
306
views
How can you bound the error of an approximation without knowing the optimal solution?
I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length ...
- 889
14
votes
1
answer
312
views
Approximation of minimum bandwidth on binary trees
Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes.
The decision problem is NP-complete even for ...
- 4,313
13
votes
1
answer
17k
views
What does the 2 in a 2-approximation algorithm mean?
Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
- 131
13
votes
1
answer
1k
views
Why are all problems in FPTAS also in FPT?
According to the Wikipedia article on polynomial-time approximation schemes:
All problems in FPTAS are fixed-parameter tractable.
This result surprises me - these classes seem to be totally ...
- 8,937
11
votes
2
answers
4k
views
What is a bicriteria approximation algorithm?
What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization?
This is where I came across it: cis.upenn....
- 289
11
votes
2
answers
178
views
Does #$P$-Completeness imply approximation hardness?
Let $\Pi$ be some counting problem which is known to be #$P$-Complete.
Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
- 2,594
11
votes
1
answer
1k
views
Average length of s-t (simple) paths in a directed graph
Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
- 245
10
votes
3
answers
10k
views
Difference between heuristic and approximation algorithm?
i have a problem regarding the following situation.
I have two arrays of numbers like this:
...
- 337
10
votes
2
answers
4k
views
Knapsack Greedy Approximation: Worst Case
I am currently studying approximation algorithms and I have run into an issue with a study problem.
The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
- 201
10
votes
1
answer
326
views
Hardness of approximating 0-1 integer programs
Given a $0,1$ (binary) integer program of the form:
$$
\begin{array}{lll}
\text{min} & f(x) & \\
\text{s.t.} & A x = b \\
& x_i \ge 0 & \quad \forall i\\
& x_i \in \{0,1\} &...
- 103
10
votes
1
answer
178
views
Mathematical optimization on a noisy function
Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x \...
D.W.♦
- 143k
10
votes
2
answers
251
views
Is this combinatorial optimisation problem similar to any known problem?
The problem is as follows:
We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
- 391
10
votes
0
answers
155
views
Complexity class for probabilistic approximation algorithms with bounded error
What's the name of a complexity class of
optimization problems that have
"bounded error probabilistic approximation algorithms"?
Bounded error probabilistic version of APX
(as BPP is bounded error ...
- 560
9
votes
2
answers
2k
views
Looping and branching with Algorithmic Differentiation
Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...
- 205
9
votes
2
answers
235
views
Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$
Let $L_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.
I need to prove that there exists $\epsilon'$ ...
- 511
9
votes
1
answer
2k
views
How do GPUs compute sines?
I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer.
Initially, I was thinking that in order to make the computations as fast as ...
- 193
9
votes
2
answers
658
views
Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Consider the following local search approximation algorithm for the unweighted max cut problem:
start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
- 113
9
votes
1
answer
578
views
Hardness of approximating Minimum Cardinality Exact Cover
The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.
Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for ...
- 520
9
votes
1
answer
363
views
2D interval scheduling problem
Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
- 364
8
votes
3
answers
654
views
What is the name of this logistic variant of TSP?
I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
- 22.1k
8
votes
2
answers
3k
views
Why is Savage's Vertex Cover algorithm a 2-approximation?
Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem.
Given graph $G$, start at arbitrary node and traverse $G$ depth-first
Obtain DFS tree $T$
return $V_C =$...
- 343
8
votes
2
answers
3k
views
Providing Tight Example in Approximation Algorithm Analysis
Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.
Do I now need to come up with an example of generic size $n$ or does it suffice to ...
- 81
8
votes
1
answer
114
views
What is the approximation ratio of this bin-backing algorithm?
Consider the following algorithm for bin packing:
Initially, sort the items by their size.
Put the largest item in a new bin.
Fill the bin with small items in ascending order of size, up to the ...
- 5,726
8
votes
1
answer
6k
views
Balanced Weight Distribution in Bins/Buckets
Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is ...
- 211
8
votes
1
answer
510
views
The heaviest induced subgraph problem
I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
- 131
8
votes
0
answers
156
views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
- 4,093
8
votes
0
answers
86
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
- 315
8
votes
0
answers
1k
views
Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)
If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem?
(...
- 81
7
votes
3
answers
2k
views
What is the fastest algorithm to approximate an irrational number with specified precision?
Problem Background:
Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
- 81
7
votes
2
answers
1k
views
Why does this graph show the tightness of MST heuristic's 2-approximation bound?
This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a ...
- 343
7
votes
1
answer
1k
views
Approximation algorithm for Feedback Arc Set
Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set.
I want to find out about is ...
- 73
7
votes
1
answer
447
views
Are there any problems in $APX - PTAS$ that are not $APX$-complete?
I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the ...
- 686
7
votes
1
answer
416
views
Approximation algorithms for NP-complete problems
Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation ...
- 560
7
votes
1
answer
311
views
Does $\#W$[1]-hardness imply approximation hardness?
Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$.
Assume that $\Pi$ is $\#W$[...
- 2,594
7
votes
1
answer
483
views
Inapproximability result implies apx-hardness?
If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?
- 145
7
votes
1
answer
418
views
In s-t directed graph, how to find many small cuts?
Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
- 123
7
votes
1
answer
2k
views
Line smoothing algorithm that perserve data uniformity
Intro:
I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels
lets say i have ...
- 171
6
votes
2
answers
1k
views
Difference between approximation scheme and approximation algorithm?
What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?
- 83
6
votes
1
answer
866
views
$1+\epsilon$ approximation for inapproximable problems
I am currently confused by the following situation:
1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can ...
- 63
6
votes
2
answers
970
views
Example for a non-trivial PCP verifier for an NP-complete problem
During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating
$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.
I understand the ...
- 71k
6
votes
1
answer
328
views
MAXSAT approximation
We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least ...
- 344
6
votes
2
answers
3k
views
What is inapproximability of NP-hard problems?
Recently I have come across a paper which talks of "(1+ε)-inapproximability" and of "logarithmic approximation".
While I have a basic knowledge of computational complexity (I more or less know what ...
6
votes
1
answer
2k
views
Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?
I read a theorem which states that:
If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant ...
- 699