# 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
Filter by
Sorted by
Tagged with
271 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 ...
391 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 ...
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$ ...
328 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 ...
404 views

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 ...
113 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 ...
514 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 ...
### Can one optimize the probability that an identity is satisfied until the probability is $1$?
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) ...