Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
601
questions
1
vote
0
answers
60
views
Reference for approximation algorithms [closed]
what is the best book to gain an introductory understanding of approximation algorithms? I'm looking for something along the lines of the Sedgewick, that has examples written in a well known language ...
- 339
1
vote
1
answer
63
views
Perturbation of a vector
Given a vector $x=(x_1,\cdots,x_n)$ such that $0\leq x_i \leq1$ and $\sum_{i=1}^n x_i=1$. I would like to find a vector $x^*$ such that ($l_1$ norm ) $||x-x^*||_1\leq \delta$, where $\delta >0$.
...
- 367
10
votes
2
answers
272
views
Is this combinatorial optimisation problem similar to any known problem?
The problem is as follows:
We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
- 391
0
votes
1
answer
3k
views
Sorted-greedy for Load Balancing Problem
In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of ...
- 11
-1
votes
3
answers
78
views
Can approximation help find the exact answer?
Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in ...
- 101
1
vote
1
answer
267
views
Anagrams solver based on transitions probability
I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
- 21
1
vote
1
answer
254
views
Subset-sum approximation algorithm running time
in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$
Essential part of this algorithm is trimming. On every step you delete all numbers which close ...
- 169
2
votes
2
answers
5k
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 ...
- 175
1
vote
0
answers
32
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 ...
- 632
0
votes
1
answer
119
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$ ...
- 1,944
17
votes
1
answer
22k
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?
- 171
8
votes
1
answer
7k
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 is ...
- 211
1
vote
0
answers
53
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 ...
- 11
3
votes
1
answer
272
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 ...
- 31
2
votes
2
answers
141
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 ...
- 632
1
vote
3
answers
807
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 ...
- 59
2
votes
1
answer
2k
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 ...
- 83
1
vote
1
answer
48
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 ...
- 487
0
votes
2
answers
51
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?
- 29
3
votes
1
answer
358
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 ...
- 61
2
votes
1
answer
594
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 ...
- 213
32
votes
7
answers
45k
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 ...
- 443
4
votes
1
answer
104
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 ...
- 1,721
7
votes
1
answer
416
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 $\#W$[...
- 2,634
11
votes
2
answers
182
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$)?
- 2,634
1
vote
0
answers
42
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
1
answer
63
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 flow ...
- 131
5
votes
1
answer
233
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 ...
- 349
11
votes
2
answers
6k
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: cis.upenn....
- 289
3
votes
1
answer
295
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 ...
- 33
1
vote
0
answers
32
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,721
1
vote
1
answer
27
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?
- 11
2
votes
1
answer
596
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 ...
- 139
0
votes
1
answer
47
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 ...
- 109
1
vote
1
answer
107
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 ...
- 502
1
vote
1
answer
89
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 ...
9
votes
1
answer
3k
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 ...
- 193
3
votes
0
answers
89
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 $f_i$...
- 3,677
1
vote
1
answer
377
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 ...
- 13
10
votes
0
answers
159
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 ...
- 580
2
votes
1
answer
220
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".
Decision problem: "Given $n$, find an object with a size of at least $n$, or reply ...
- 5,994
5
votes
1
answer
805
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 ...
- 5,994
1
vote
0
answers
75
views
Quadratic programming problem involving permutation matrices [closed]
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 ...
- 11
7
votes
1
answer
468
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 ...
- 580
2
votes
1
answer
652
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 ...
- 69
1
vote
1
answer
690
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 ...
- 113
2
votes
0
answers
788
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 ...
- 73
4
votes
2
answers
403
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 . ...
- 73
1
vote
1
answer
2k
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 ...
- 335