Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
37
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.6k
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 ...
- 9,037
10
votes
1
answer
194
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.♦
- 156k
19
votes
2
answers
13k
views
17
votes
1
answer
22k
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?
- 171
11
votes
2
answers
5k
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
0
votes
2
answers
2k
views
Vertex cover of bipartite graph
A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.
From codeforces,
...
- 394
32
votes
7
answers
43k
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 ...
- 443
8
votes
3
answers
688
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.5k
5
votes
1
answer
797
views
NP-complete decision problems - how close can we come to a solution?
After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ...
- 5,720
5
votes
0
answers
703
views
2 Dimensional Subset Sum: looking for information
I do not know if this problems exists with a different name, if it is, I could not find it.
The problem is this:
Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
- 111
4
votes
2
answers
3k
views
without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?
In the text book, Introduction to Algorithm, 3rd Edition.
In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says:
I am wondering how triangle ...
- 335
1
vote
1
answer
694
views
Derandomization of vertex cover algorithm
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.
Add to ...
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
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
8
votes
2
answers
3k
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 ...
- 195
6
votes
1
answer
460
views
Minimal Steiner Tree in unweighted directed graph
I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
- 161
6
votes
2
answers
1k
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 ...
- 72k
5
votes
2
answers
512
views
Approximation ratio when optimal solution is $0$
This might be a basic technicality but I'd like to make sure how to handle it.
The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $...
- 530
5
votes
1
answer
224
views
What is the significance of the vector dimension in semidefinite programming relaxations?
Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.
So, we first write down an integer quadratic ...
- 339
5
votes
1
answer
922
views
Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED
NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really ...
- 53
4
votes
1
answer
842
views
Best data structure for high dimensional nearest neighbor search
I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I'...
- 141
3
votes
1
answer
259
views
Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?
Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it ...
- 187
3
votes
1
answer
1k
views
Big-O / $\tilde{O}$ -notation with multiple variables when function is decreasing in one of its arguments
Say we have an algorithm that
takes an input a triple
($X$, $A$, $\epsilon$),
where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are ...
- 51
3
votes
5
answers
941
views
What does big O mean as a term of an approximation ratio?
I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem.
The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$.
...
Jacob Fogner
3
votes
1
answer
7k
views
Correctness proof: 2-approximation of greedy matching-algorithm
Input: number of edges and vertices, and array of all edges in graph.
Output: array of edges that construct a matching, so that:
$$\frac{\text{the number of edges in this matching}}{\text{the number ...
- 33
3
votes
2
answers
418
views
Minimising sum of consecutive points distances Manhattan metric
I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points ...
- 9,425
2
votes
1
answer
2k
views
Bottleneck TSP with MST
There is a problem I don't know the answer too.
The 3 approximation for the bottleneck TSP that involves first getting the MST.
I have not been able to come up with the right "shortcut" method so far.
...
- 39
2
votes
1
answer
1k
views
How to correctly define the ratio of an approximation algorithm?
For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal ...
- 305
1
vote
1
answer
55
views
Weighted interval scheduling with m-machines ---greedy solution with approximation factor
Weighted interval scheduling with m-machines
('Weighted interval scheduling with m-machines')
I encountered the problem of weighted interval scheduling on m identical machines (as discussed in the ...
- 11
1
vote
1
answer
85
views
About showing algorithmic gap instance for the Goemans-Williamson SDP
Using usual notation we have,
$SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$
where we mean,
$SDP(G)$ = The maximum value that the SDP finds of the objective ...
- 493
1
vote
1
answer
60
views
Communication complexity of equality gap problem
I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by:
$$f_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at ...
- 11.5k
1
vote
1
answer
131
views
Seeking Efficient Approximation Algorithm for Adaptation of TSP
Consider the following adaptation of the traveling salesman problem:
Given a complete, undirected graph $G$ with nonnegative edge weights,
color each vertex either red or blue. Find the shortest ...
- 11
0
votes
1
answer
36
views
Weighted interval scheduling on K-identical machines --- approximation factor
This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.
As suggested by @D.W., I will present the problem more comprehensively.
$\textbf{...
- 11
0
votes
1
answer
59
views
Geometric Set Cover in one dimension
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 63
-1
votes
1
answer
435
views
How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
- 25
-1
votes
1
answer
77
views
acyclic and disjoint union
I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition?
Thanks, ...
- 15