Questions tagged [approximation-algorithms]
An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that is within a constant factor of the optimum. Hardness of approximation is one way to separate NP-hard problems.
11
questions
10
votes
1
answer
288
views
Confusion with practically implementing rational approximations
Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
6
votes
1
answer
1k
views
Searching for an inhomogeneous diophantine approximation algorithm
Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, what is an algorithm that will provide coprime integers $a$ ...
6
votes
0
answers
460
views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
5
votes
1
answer
1k
views
Hypergraph Chromatic Number vs Degree, Clique-Size
For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
4
votes
2
answers
344
views
Can you solve this problem using a finite number of queries?
Let $g:[0,1]\to[0,1]$ be a continuous monotonically-increasing function. You can access $g$ using queries of two kinds:
Given $x\in[0,1]$, return $g(x)$.
Given $y\in[0,1]$, return $g^{-1}(y)$.
Given ...
3
votes
3
answers
127
views
Detecting slow growth in a finite number of queries
The following question was asked at Can you solve this problem using a finite number of queries?
:
Let $g:[0,1]\to[0,1]$ be a continuous monotonically-increasing function. You can access $g$ using ...
3
votes
3
answers
511
views
Determining Roots of a Polynomial with Interval Estimates of Coefficients
Let $f$ be a monic univariate polynomial with real coefficients:
$$f_A(x) = x^n + a_{n-1}x^{n-1} + ... + a_{0}$$
The values of $A=(a_{n-1},...,a_0)$ are unknown, but are estimated as $B=(b_{n-1},...,...
3
votes
2
answers
720
views
Approximation of curves
When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have ...
2
votes
0
answers
125
views
Can one optimize the probability that an identity is satisfied until the probability is $1$?
I wonder how well one can obtain algebraic structures that satisfy interesting algebraic identities by simply slowly modifying those algebraic structures until they satisfy the required identities. I ...
1
vote
0
answers
148
views
Minimum delay path in time-dependent graph
Given a time-dependent graph, where each edge $e$ is on for certain time intervals and off otherwise. Traversing $e$ incurs a delay $d_e$ and is possible only when $e$ is on. Given a pair of vertices $...
0
votes
2
answers
482
views
Relaxed path decomposition of a graph
Definition
Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...