Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
577
questions
2
votes
0
answers
75
views
Throughput measure
I have to implement a limitation algorithm in order to avoid to reach a throughput limit imposed by the service I'm interacting with.
The limit is specified as «N request over 1 day» where N is of ...
- 121
6
votes
1
answer
882
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
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
1
answer
343
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\} &...
- 203
0
votes
2
answers
392
views
Implications of truncation of numbers when converted into binary
I have been posed with a question whereby a computer truncates numbers to x number of digits. Due to this, if this computer is trying to store a decimal number which has a binary equivalent greater ...
- 1
3
votes
5
answers
931
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
9
votes
2
answers
240
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
3
votes
1
answer
146
views
Show that approximation ratio for a convex hull algorithm is $\pi/2$
Facts: n points in the plane, each has one of k colors, all k colors are represented.
Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small ...
- 1,783
1
vote
1
answer
198
views
For what values of A and B is the gap-VC-[A,B] problem NP-HARD?
For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or $B=\frac{3}{4},A=\...
- 1,697
3
votes
1
answer
4k
views
2OPT Approximation Algorithm for Multiway Cut Problem
In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum
set of edges in $E$ whose removal ...
lam lae
7
votes
1
answer
507
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?
- 155
6
votes
2
answers
842
views
Randomized Rounding of Solutions to Linear Programs
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
- 3,857
4
votes
2
answers
1k
views
Algorithm to pack any small boxes into a big box
I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
- 141
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
3
votes
2
answers
353
views
Given many partial orders, check them for consistency and report any that are not consistent
Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything.
I am also given a collection of ...
D.W.♦
- 152k
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
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
2
votes
1
answer
344
views
$L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$
If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$?
Since for example metric-TSP is in APX, but it is not approximable within 220/219 ...
- 23
2
votes
2
answers
4k
views
Partition of a set of integer into 3 subsets of approximately equal sum
I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:
"A hard working mom bought several fruits with different nutritional values for ...
Julian J. Tejera
1
vote
1
answer
3k
views
3-dimensional matching approximation algorithm (implementation details)
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?
$X, Y,...
- 13
7
votes
1
answer
458
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
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
22
votes
1
answer
540
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
5
votes
1
answer
899
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
8
votes
3
answers
683
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.4k
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
14
votes
1
answer
334
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,377