Questions about algorithms that solve problems up to some bounded error.
3
votes
1answer
25 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 ...
0
votes
0answers
65 views
Hardness of approximation of vertex cover [closed]
I have the following proof of hardness of approximation of vertex cover but I am not sure if it is correct:
I will assume that Max3Sat is hard to approximate for some constant $\rho<1$.
I did the ...
2
votes
1answer
60 views
Euclidean Steiner Tree Question in Approximation Algorithms
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
...
0
votes
1answer
46 views
What's the vertex cover of the null graph?
Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.
2
votes
0answers
27 views
Light approximation for shortest path tree
I am looking for the paper : "B. Awerbuch, A. Baratz, and D. Peleg, Efficient broadcast and light-weight spanners, Manuscript, (1991)."
It claims that we can build $(\alpha ,1+\frac{4}{\alpha -1})-LAST$ ...
1
vote
1answer
57 views
Hardness of approximation of the 3 colorability problem
If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?
I also have some sort of ...
1
vote
1answer
30 views
reducing Max3SAT to Max2sat
I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi $ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?
0
votes
2answers
56 views
proving $P \subseteq PCP(0,O(log(n))$
I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to ...
2
votes
1answer
70 views
Finding a tree that approximates the distances and total weights
Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d_G(r,x) \le d_T(r,x) \le 3 \cdot ...
8
votes
1answer
70 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 ...
4
votes
1answer
45 views
Prize collecting steiner tree
I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
2
votes
0answers
18 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 ...
5
votes
1answer
101 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 ...
3
votes
3answers
175 views
Difference between heuristic and approximation algorithm?
i have a problem regarding the following situation.
I have two arrays of numbers like this:
...
5
votes
1answer
63 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\vec{x} = \vec{b} & \quad \forall i\\
&x_i\ge 0 & \quad \forall ...
0
votes
2answers
37 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
vote
0answers
38 views
Arora's PTAS for the k-MST-Problem
I've just read Arora's paper "Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems". On page 8 Arora says that the dynamic programming procedure can be changed to get a ...
2
votes
5answers
114 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)$.
...
8
votes
2answers
116 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'$ ...
3
votes
1answer
47 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
vote
1answer
44 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 ...
2
votes
1answer
94 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 ...
1
vote
0answers
80 views
Proving that no deterministic algorithm can be better than a 3-approximation
There are three popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the ...
3
votes
1answer
51 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?
5
votes
2answers
119 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
votes
2answers
110 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 ...
7
votes
1answer
201 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 ...
3
votes
2answers
84 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 ...
5
votes
2answers
112 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 ...
8
votes
1answer
109 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 ...
2
votes
1answer
180 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 ...
2
votes
2answers
333 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 ...
1
vote
1answer
228 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, ...
7
votes
1answer
123 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 ...
6
votes
0answers
198 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?
...
10
votes
0answers
161 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 ...
4
votes
1answer
182 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 ...
5
votes
3answers
125 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 ...
18
votes
2answers
446 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. ...
10
votes
1answer
154 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 ...
