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

learn more… | top users | synonyms (1)

-1
votes
0answers
19 views

k-maximally link disjoints paths with weight constraints

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
4
votes
1answer
19 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
5
votes
0answers
34 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is ...
10
votes
2answers
86 views

Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
1
vote
0answers
35 views

Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$ \leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I ...
3
votes
1answer
25 views

Packing unsplittable flows problem

For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ : Let's define as ...
3
votes
1answer
17 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 ...
1
vote
1answer
59 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: ...
3
votes
1answer
37 views

Hardness of approximating hitting set

Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that 1) it is NP-hard to approximate the cost of the optimal solution to a ...
1
vote
0answers
15 views

Approximation scheme for finding best product of matrices that minimizes $||Ax - y||$ for given $x,y$

Given a set of $N$ $n \times n$ matrices $A_1,\ldots,A_N$, and two vectors $x,y$, the problem is to find a product of up to $K$ matrices $A = A_{j_1}A_{j_2}\cdots A_{j_k}$ so that $Ax$ is as close to ...
-1
votes
0answers
36 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
17 views

Estimating (c-1) from approximation of c

If we have a FPRAS for approximating the quantity c, can we get another FPRAS for estimating (c-1) using the estimation of c?
1
vote
1answer
85 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
40 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
48 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
19 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
131 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
44 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
70 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
64 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
145 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
39 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
5
votes
1answer
86 views

Approximation algorithms for NP-complete problems

Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation ...
1
vote
1answer
123 views

Finding an instance of an n-element set cover

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
1
vote
1answer
127 views

Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

I'm given this problem: Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen ...
1
vote
0answers
135 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
117 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
vote
1answer
170 views

Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first ...
2
votes
1answer
169 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 ...
-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
199 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 ...
0
votes
0answers
39 views

Constant factor approximation of hypergraph maxdicut

The MAXDICUT problem on a directed graph $G$ is where one is given integer $t$ and a graph $G$ and one has to decide if there is a subset $S \subset \mathcal{V}(G)$ such that $$|\{(i\rightarrow ...
6
votes
1answer
133 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
134 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
130 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
148 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
201 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
261 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
118 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
414 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
63 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
80 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
119 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
108 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
161 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
132 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
51 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
87 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
67 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
163 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 ...