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

learn more… | top users | synonyms (1)

1
vote
0answers
17 views

MaxSNP flow problems

Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
0
votes
1answer
54 views

Approximate the order of summation of two vectors

Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ ...
3
votes
1answer
23 views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
3
votes
1answer
34 views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which ...
1
vote
0answers
43 views

Approximation for fewest incompatibilities in a scheduling algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
3
votes
1answer
87 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
2
votes
1answer
19 views

Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
1
vote
2answers
66 views

A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
2
votes
1answer
35 views

Proving approximation ratio

We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking ...
1
vote
1answer
19 views

Hardness and approximation of a problem with a parameter

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could ...
0
votes
2answers
35 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
44 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
47 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
309 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
26 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
46 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
103 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
26 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
132 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
40 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
16 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
40 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
18 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
105 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
42 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
53 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
150 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
47 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
79 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
91 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
80 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
156 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
89 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
148 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
164 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
156 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
133 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
328 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
207 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
202 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
136 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
143 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
142 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
160 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
229 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 ...