Questions about algorithms that solve problems up to some bounded error.
1
vote
1answer
57 views
3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the ...
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
58 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
35 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
48 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
315 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
27 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
137 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
41 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
48 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
331 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 ...
