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

learn more… | top users | synonyms

-1
votes
0answers
27 views

What is the Unique Games Conjecture? [closed]

What is the unique game conjecture in relatively simple words? What are the consequences of proving it or disproving it? Does it has any relation to game theory? Why is there "game" in the name?
1
vote
1answer
71 views

Approximation algorithms for Euclidean Traveling Salesman [closed]

I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this ...
0
votes
1answer
37 views

Can someone interpret what this is asking for

I have this programming problem, but I really cant figure out what it wants me to do. Heres what it is: The cube root of a number can be found based on the observation that, if $t$ is an ...
1
vote
1answer
36 views

Wave propagation in digital image

I believe the following question in summary is: How to approximate Euclidean distance in a digital plane? When a pebble falls on a calm surface of water a circular wave propagates. I want to color ...
1
vote
1answer
14 views

Error estimates of piecewise-linear curve approximations

In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about ...
5
votes
1answer
110 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 ...
3
votes
0answers
41 views

What functions are easy to optimize?

Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function ...
1
vote
1answer
54 views

Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
0
votes
1answer
42 views

Using approximations to optimization problems for threshold problems

Many problems in computer science come in two flavors: Optimization problem: "Find an object with the largest size". Threshold problem: "Given $n$, find an object with a size of at least $n$, or ...
4
votes
1answer
121 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 ...
1
vote
0answers
115 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
4
votes
2answers
110 views

NP-hardness and FPTAS

I have a problem in understanding how to prove the following question. Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers. Define $$L_Q^* =\{(x_0,1^k) : \exists x . ...
-1
votes
1answer
40 views

Is a non-perfect improvement and optimisation?

In real word problems, the influence of multiple not perfectly known factors results in using heuristics instead of mathemacial solutions that calculates a perfect value from only precisly defined ...
11
votes
1answer
192 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 ...
7
votes
1answer
129 views

Estimating the time until we obtain five-in-a-row?

Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker ...
7
votes
1answer
109 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 ...
6
votes
2answers
119 views

Difference between approximation scheme and approximation algorithm?

What is the difference between approximation schemes and approximation algorithms? Why do we study approximation schemes?
6
votes
1answer
130 views

Approximability of the edge-disjoint shortest paths problem

In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize ...
8
votes
1answer
161 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 ...
4
votes
2answers
188 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 ...
4
votes
1answer
105 views

Subset optimization problem

Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. ...
4
votes
1answer
406 views

About metric TSP instances

Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that ...
4
votes
1answer
54 views

Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?

In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal ...
0
votes
0answers
66 views

Aproximation algorithm for histogram

This is my first question, so please, be soft on me. I have a following problem: I'm a programmer not a mathematician, I don't often understand pure mathematical language and marks or symbols, I ...
3
votes
1answer
92 views

How approximate are “approximate” nearest neighbor (ANN) search algorithms?

Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are. If I have a (more or less) randomly distributed point ...
3
votes
1answer
92 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 ...
2
votes
1answer
107 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
116 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.
1
vote
0answers
50 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
79 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
62 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?
-1
votes
2answers
114 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
85 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 ...
10
votes
1answer
209 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
84 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
26 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 ...
6
votes
1answer
151 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 ...
4
votes
3answers
933 views

Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
8
votes
1answer
88 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
108 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 ...
2
votes
5answers
233 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)$. ...
10
votes
2answers
124 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
61 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
67 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
342 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 ...
4
votes
1answer
101 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
161 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
213 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
362 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
111 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 ...