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

learn more… | top users | synonyms (1)

0
votes
2answers
32 views

What all can a valid approximation algorithm access?

For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?
0
votes
0answers
41 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
2
votes
1answer
36 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
11
votes
2answers
239 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 ...
4
votes
1answer
22 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
38 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 ...
11
votes
2answers
95 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
18 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
79 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
38 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
37 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
96 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
41 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
49 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
20 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
141 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
45 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
73 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 ...
6
votes
0answers
88 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
0
votes
1answer
69 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
148 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
41 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 ...
6
votes
1answer
88 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
132 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
129 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
145 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
127 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
209 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
176 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
41 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
201 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 ...
6
votes
1answer
135 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
135 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
131 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
154 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
217 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
267 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
123 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
66 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
81 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 ...
4
votes
1answer
132 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
114 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
136 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
54 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$ ...