Questions tagged [approximation]

Questions about algorithms that solve problems up to some bounded error.

Filter by
Sorted by
Tagged with
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. ...
Ran G.'s user avatar
  • 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 ...
templatetypedef's user avatar
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.'s user avatar
  • 156k
19 votes
2 answers
13k views

PTAS definition vs. FPTAS

From what I read in the ...
M a m a D's user avatar
  • 1,509
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?
Hrishikesh's user avatar
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....
Suhas Lohit's user avatar
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, ...
Manoharsinh Rana's user avatar
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 ...
moraes's user avatar
  • 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 ...
Juho's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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$ ...
Harry's user avatar
  • 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 ...
xiaohan2012's user avatar
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 ...
bruce_springsteen's user avatar
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 (...
woliveirajr's user avatar
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: ...
user6697's user avatar
  • 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 ...
iago-lito's user avatar
  • 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 ...
t.pimentel's user avatar
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 ...
Raphael's user avatar
  • 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 $...
Manuel Lafond's user avatar
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 ...
Zur Luria's user avatar
  • 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 ...
Casper's user avatar
  • 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'...
mavillan's user avatar
  • 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 ...
Vimal Raj Sharma's user avatar
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 ...
JoeNash's user avatar
  • 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)$. ...
user avatar
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 ...
inquiro's user avatar
  • 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 ...
Evil's user avatar
  • 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. ...
mmmi's user avatar
  • 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 ...
9bi7's user avatar
  • 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 ...
EddieG's user avatar
  • 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 ...
gradstudent's user avatar
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 ...
nir shahar's user avatar
  • 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 ...
Jake's user avatar
  • 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{...
EddieG's user avatar
  • 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 ...
Sandra's user avatar
  • 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 ...
ConScience's user avatar
-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, ...
DarkDragon's user avatar